codeforces 487B Strip

http://www.elijahqi.win/archives/1355
Alexandra has a paper strip with n numbers on it. Let’s call them ai from left to right.

Now Alexandra wants to split it into some pieces (possibly 1). For each piece of strip, it must satisfy:

Each piece should contain at least l numbers.
The difference between the maximal and the minimal number on the piece should be at most s.
Please help Alexandra to find the minimal number of pieces meeting the condition above.

Input
The first line contains three space-separated integers n, s, l (1 ≤ n ≤ 105, 0 ≤ s ≤ 109, 1 ≤ l ≤ 105).

The second line contains n integers ai separated by spaces ( - 109 ≤ ai ≤ 109).

Output
Output the minimal number of strip pieces.

If there are no ways to split the strip, output -1.

Examples
Input
7 2 2
1 3 1 2 4 1 2
Output
3
Input
7 2 2
1 100 1 100 1 100 1
Output
-1
Note
For the first sample, we can split the strip into 3 pieces: [1, 3, 1], [2, 4], [1, 2].

For the second sample, we can’t let 1 and 100 be on the same piece, so no solution exists.

强啊 这我哪会啊

膜了一番 zhx的题解发现他单调队列用的real娴熟 首先可以利用单调队列求出L【i】表示以这个数为右端点 他的左端点可以延伸到哪里 dp的时候我用单调队列维护一下 每次做的时候先把i-l这个位置加入 并且把末端弹出 因为要求最小长度是l 然后再用队首的值去更新我的答案 有可能无解 就保持原数组inf就可以 输出的时候判断一下就行

#include<cstdio>
#include<deque>
#include<cstring>
#define inf 0x7f7f7f7f
#define N 110000
using namespace std;
inline char gc(){
    static char now[1<<16],*S,*T;
    if(S==T){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF; }
    return *S++;
}
inline int read(){
    int x=0,f=1;char ch=gc();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=gc();}
    while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();}
    return x*f;
}
struct node{
    int id,value;
};
deque<node> q,q1,q2;
int a[N],L[N],l,s,n,f[N];
int main(){
//  freopen("cf.in","r",stdin);
    n=read();s=read();l=read();
    for (int i=1;i<=n;++i) a[i]=read();int p=0;
    for (int i=1;i<=n;++i){
        while (!q1.empty()&&a[i]+s<q1.front().value) p=q1.front().id+1,q1.pop_front();
        while (!q2.empty()&&a[i]-s>q2.front().value) p=q2.front().id+1,q2.pop_front();
        L[i]=p;node tmp;tmp.id=i;tmp.value=a[i];
        while (!q1.empty()&&a[i]>q1.back().value) q1.pop_back();q1.push_back(tmp);
        while (!q2.empty()&&a[i]<q2.back().value) q2.pop_back();q2.push_back(tmp);
    }memset(f,0x7f,sizeof(f));f[0]=0;
    for (int i=l;i<=n;++i){
        while (!q.empty()&&q.back().value>f[i-l]) q.pop_back();
        node tmp;tmp.value=f[i-l];tmp.id=i-l;q.push_back(tmp);
        while (!q.empty()&&q.front().id<L[i]-1) q.pop_front();
        if (!q.empty()&&q.front().value!=inf) f[i]=q.front().value+1;
    }
    if (f[n]==inf) printf("-1");else printf("%dn",f[n]);
    return 0;
}

最后

以上就是安静黑米为你收集整理的codeforces 487B Strip的全部内容，希望文章能够帮你解决codeforces 487B Strip所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。