CodeForces 487B Strip

106 阅读 0 评论 70 点赞

我是靠谱客的博主谦让大神，这篇文章主要介绍CodeForces 487B Strip，现在分享给大家，希望可以做个参考。

这道题的思路我觉得又点绕要先处理处区间最大差值，在进行DP，不过DP 很简单f[i] = min(f[j])+1，看代码：

复制代码

#include<cstdio>
#include<iostream>
using namespace std;
const int inf = 1<<30;
const int MAXN = 1e5 + 5;
int mn[MAXN][20], mx[MAXN][20], a[MAXN], f[MAXN], n, s, L;
int query(int l, int r) {   //询问区间最大差值
    int k = 0;
    while ((1 << (k+1)) <= r - l + 1) k++;
    return max(mx[l][k], mx[r-(1<<k)+1][k]) - min(mn[l][k], mn[r-(1<<k)+1][k]);
}
int main()
{
    scanf("%d%d%d", &n, &s, &L);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", mn[i] + 0);
        mx[i][0] = mn[i][0];
    }
    for(int j = 1; (1<<j) <= n; j++) for(int i = 1; i + (1<<j) - 1 <= n; i++) {   //RMQ
            mn[i][j] = min(mn[i][j-1], mn[i+(1<<(j-1))][j-1]);
            mx[i][j] = max(mx[i][j-1], mx[i+(1<<(j-1))][j-1]);
    }
    fill_n(f, n+1, inf);
    int mv = f[0] = 0;
    for(int i = L; i <= n; i++) {
        while (i - mv >= L && (query(mv + 1, i) > s || f[mv] == inf))
            mv++;
        if (i - mv >= L)
            f[i] = min(f[i], f[mv] + 1);
    }
    if (f[n] == inf)
        f[n] = -1;
    printf("%dn", f[n]);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<cstdio>
#include<iostream>
using namespace std;
const int inf = 1<<30;
const int MAXN = 1e5 + 5;
int mn[MAXN][20], mx[MAXN][20], a[MAXN], f[MAXN], n, s, L;
int query(int l, int r) {   //询问区间最大差值
    int k = 0;
    while ((1 << (k+1)) <= r - l + 1) k++;
    return max(mx[l][k], mx[r-(1<<k)+1][k]) - min(mn[l][k], mn[r-(1<<k)+1][k]);
}
int main()
{
    scanf("%d%d%d", &n, &s, &L);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", mn[i] + 0);
        mx[i][0] = mn[i][0];
    }
    for(int j = 1; (1<<j) <= n; j++) for(int i = 1; i + (1<<j) - 1 <= n; i++) {   //RMQ
            mn[i][j] = min(mn[i][j-1], mn[i+(1<<(j-1))][j-1]);
            mx[i][j] = max(mx[i][j-1], mx[i+(1<<(j-1))][j-1]);
    }
    fill_n(f, n+1, inf);
    int mv = f[0] = 0;
    for(int i = L; i <= n; i++) {
        while (i - mv >= L && (query(mv + 1, i) > s || f[mv] == inf))
            mv++;
        if (i - mv >= L)
            f[i] = min(f[i], f[mv] + 1);
    }
    if (f[n] == inf)
        f[n] = -1;
    printf("%dn", f[n]);
    return 0;
}