频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
BZOJ 3904 最长上升子序列 lkids 线段树
2015-03-08 11:11:14         来源:世界  
收藏   我要投稿

题目大意:给定一个序列,求以较小数开始的锯齿子序列,使相邻两项之间差值不小于k

令f[i][0]表示第i个数为序列中的较大值的最长子序列

f[i][1]表示第i个数为序列中的较小值的最长子序列

暴力转移是O(n^2)的

我们发现决策点的值都是连续的一段区间 因此用线段树维护一下就行了

(真简略)

#include 
#include 
#include 
#include 
#define M 200200
using namespace std;
template struct Segtree{
	Segtree *ls,*rs;
	int val;
	Segtree():ls(0x0),rs(0x0),val(_) {}
	friend void Update(Segtree *&p,int x,int y,int l,int r,int val)
	{
		int mid=x+y>>1;
		if(!p) p=new Segtree;
		if(x==l&&y==r)
		{
			p->val=max(p->val,val);
			return ;
		}
		if(r<=mid)
			Update(p->ls,x,mid,l,r,val);
		else if(l>mid)
			Update(p->rs,mid+1,y,l,r,val);
		else
			Update(p->ls,x,mid,l,mid,val) , Update(p->rs,mid+1,y,mid+1,r,val);
	}
	friend int Get_Ans(Segtree *p,int x,int y,int pos)
	{
		int mid=x+y>>1;
		if(!p) return _;
		if(x==y) return p->val;
		if(pos<=mid)
			return max(Get_Ans(p->ls,x,mid,pos),p->val);
		else
			return max(Get_Ans(p->rs,mid+1,y,pos),p->val);
	}
};
Segtree< 0> *tree0=new Segtree< 0>;
Segtree<-1> *tree1=new Segtree<-1>;
int n,k,ans;
int a[M],f[M][2];
int main()
{
	int i;
	cin>>n>>k;
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		if(a[i]-k>=0)
		{
			f[i][0]=Get_Ans(tree1,0,100000000,a[i]-k)+1;
			Update(tree0,0,100000000,0,a[i],f[i][0]);
		}
		if(a[i]+k<100000000)
		{
			f[i][1]=Get_Ans(tree0,0,100000000,a[i]+k)+1;
			Update(tree1,0,100000000,a[i],100000000,f[i][1]);
		}
		ans=max(ans,f[i][0]);
		ans=max(ans,f[i][1]);
	}
	cout<

点击复制链接 与好友分享!回本站首页
相关TAG标签 升子 线段 序列
上一篇:uva 10670 Work Reduction (贪心)
下一篇:C++默认构造函数
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站