概述
题意:一个数列分成若干段,满足两个条件,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;
else
pre[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("-1n");
else
printf("%dn",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的全部内容,希望文章能够帮你解决codeforces 487 B. Strip所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复