CodeForces - 487B Strip(线段树+dp+二分)

题目链接:点击查看

题目大意:给出一个长度为 n 的序列,现在要求分成尽可能少的子段,且每个子段需要满足:

  1. 最大值与最小值的差值小于等于 s
  2. 子段长度大于等于 l

题目分析:dp[ i ] 代表的是前 i 个数字分成最少的子段个数,转移方程如下:

  1. dp[ i ] = dp[ j - 1 ] + 1:第 i 项单独一段
  2. dp[ i ] = dp[ j - 2 ] + 1:第 i 项与 i - 1 项组成一段
  3. ...
  4. dp[ i ] = dp[ 0 ] + 1:第 1 ~ i 项组成一段

显然是取上面合法的前驱的最小值用来维护 dp[ i ],因为需要满足条件一,又因为子串的长度与 delta ,也就是最大值与最小值的差,成反比,所以可以二分找到 dp[ j ] 的左端点 l,而 dp[ j ] 的右端点 r 同时也被条件二限制,此时的问题就转换成了求区间 [ l , r ] 内 dp 的最小值了,这里用线段树维护一下就好,总的来说需要维护两个线段树,因为维护 dp[ i ] 的过程中需要套上一个二分,所以总的时间复杂度为 O( nlog^2n )

代码:
 

//#pragma GCC optimize(2)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
using namespace std;
     
typedef long long LL;
     
typedef unsigned long long ull;
     
const int inf=0x3f3f3f3f;

const int N=1e6+100;

namespace Seg1
{
	struct Node
	{
		int l,r,mmin,mmax;
	}tree[N<<2];
	void build(int k,int l,int r)
	{
		tree[k].l=l;
		tree[k].r=r;
		if(l==r)
		{
			scanf("%d",&tree[k].mmax);
			tree[k].mmin=tree[k].mmax;
			return;
		}
		int mid=l+r>>1;
		build(k<<1,l,mid);
		build(k<<1|1,mid+1,r);
		tree[k].mmax=max(tree[k<<1].mmax,tree[k<<1|1].mmax);
		tree[k].mmin=min(tree[k<<1].mmin,tree[k<<1|1].mmin);
	}
	int query_min(int k,int l,int r)
	{
		if(tree[k].l>r||tree[k].r<l)
			return inf;
		if(tree[k].l>=l&&tree[k].r<=r)
			return tree[k].mmin;
		return min(query_min(k<<1,l,r),query_min(k<<1|1,l,r));
	}
	int query_max(int k,int l,int r)
	{
		if(tree[k].l>r||tree[k].r<l)
			return -inf;
		if(tree[k].l>=l&&tree[k].r<=r)
			return tree[k].mmax;
		return max(query_max(k<<1,l,r),query_max(k<<1|1,l,r));
	}
}

namespace Seg2
{
	struct Node
	{
		int l,r,mmin;
	}tree[N<<2];
	void build(int k,int l,int r)
	{
		tree[k].l=l;
		tree[k].r=r;
		tree[k].mmin=inf;
		if(l==r)
			return;
		int mid=l+r>>1;
		build(k<<1,l,mid);
		build(k<<1|1,mid+1,r);
	}
	void update(int k,int pos,int val)
	{
		if(tree[k].l==tree[k].r)
		{
			tree[k].mmin=val;
			return;
		}
		int mid=tree[k].l+tree[k].r>>1;
		if(pos<=mid)
			update(k<<1,pos,val);
		else
			update(k<<1|1,pos,val);
		tree[k].mmin=min(tree[k<<1].mmin,tree[k<<1|1].mmin);
	}
	int query(int k,int l,int r)
	{
		if(l>r)
			return inf;
		if(tree[k].l>r||tree[k].r<l)
			return inf;
		if(tree[k].l>=l&&tree[k].r<=r)
			return tree[k].mmin;
		return min(query(k<<1,l,r),query(k<<1|1,l,r));
	}
}

int main()
{
#ifndef ONLINE_JUDGE
//  freopen("data.in.txt","r",stdin);
//  freopen("data.out.txt","w",stdout);
#endif
//  ios::sync_with_stdio(false);
	int n,s,len;
	scanf("%d%d%d",&n,&s,&len);
	Seg1::build(1,1,n);
	Seg2::build(1,0,n);
	Seg2::update(1,0,0);
	for(int i=1;i<=n;i++)
	{
		int l=1,r=i,mark=-1;
		while(l<=r)
		{
			int mid=l+r>>1;
			int delta=Seg1::query_max(1,mid,i)-Seg1::query_min(1,mid,i);
			if(delta<=s)
			{
				mark=mid;
				r=mid-1;
			}
			else
			{
				l=mid+1;
			}
		}
		if(mark!=-1)
			Seg2::update(1,i,Seg2::query(1,mark-1,i-len)+1);
	}
	if(Seg2::query(1,n,n)==inf)
		puts("-1");
	else
		printf("%d\n",Seg2::query(1,n,n));









    return 0;
}

 

上一篇:《Web前端开发精品课——HTML5 Canvas开发详解》——导读


下一篇:Python: 去掉字符串开头、结尾或者中间不想要的字符