本文主要是介绍codeforces 487 B. Strip，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：一个数列分成若干段，满足两个条件，1.每一段长度l>=s，2.每一段mx-mi<=s，求最小段数。
分析：一个很常见的思路，先预处理每个数最左边可行位置pre[i]，动态方程，dp[i]=min(dp[k]+1)，pre[i]-1<=k<=i-l；预处理用set，时间n+n，动态转移用线段树维护了一个最小值。（写得较挫）
#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<map>
#include<algorithm>
#include<queue>
#include<set>
#define inf 10000000
#define pi acos(-1.0)
#define eps 1e-8
#define seed 131
using namespace std;
typedef pair<int,int> pii;
typedef unsigned long long ULL;
typedef long long LL;
const int maxn=100005;
map<int,int>mp;
set<int>se;
int n,s,l;
int d[maxn];
int pre[maxn];
int dp[maxn];
int tree[maxn<<2];
int query(int L,int R,int l,int r,int rt);
void update(int L,int R,int c,int l,int r,int rt);
int main()
{scanf("%d%d%d",&n,&s,&l);for(int i=1;i<=n;i++)scanf("%d",&d[i]);int i=n,j=n+1;for(;i>=1;i--){while(1){if(i-j+1>=l){if((*(--se.end())-*se.begin())<=s){if(j==1){pre[i]=1;break;}j--;se.insert(d[j]);mp[d[j]]++;}else{if(i-j>=l)pre[i]=j+1;elsepre[i]=-1;break;}}else{if(j==1){pre[i]=-1;break;}j--;se.insert(d[j]);mp[d[j]]++;if((*(--se.end())-*se.begin())>s){pre[i]=-1;break;}}}mp[d[i]]--;if(mp[d[i]]==0)se.erase(d[i]);}dp[0]=0;memset(tree,0,sizeof(tree));for(int i=1;i<=n;i++){dp[i]=inf;if(pre[i]==-1);else if(pre[i]==1){dp[i]=1;}else if(pre[i]-1<=i-l)dp[i]=min(dp[i],query(pre[i]-1,i-l,1,n,1)+1);update(i,i,dp[i],1,n,1);}if(dp[n]==inf)printf("-1\n");elseprintf("%d\n",dp[n]);return 0;
}
void pushup(int l,int r,int rt)
{tree[rt]=min(tree[rt<<1],tree[rt<<1|1]);return;
}
void update(int L,int R,int c,int l,int r,int rt)
{if(L<=l&&R>=r){tree[rt]=c;return;}int m=(l+r)>>1;if(L<=m)update(L,R,c,l,m,rt<<1);if(R>m)update(L,R,c,m+1,r,rt<<1|1);pushup(l,r,rt);
}
int query(int L,int R,int l,int r,int rt)
{int mi=inf;if(L<=l&&R>=r){mi=min(tree[rt],mi);return mi;}int m=(l+r)>>1;if(L<=m)mi=min(mi,query(L,R,l,m,rt<<1));if(R>m)mi=min(mi,query(L,R,m+1,r,rt<<1|1));return mi;
}这篇关于codeforces 487 B. Strip的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
