hdu4521:http://acm./showproblem.php?pid=4521
题解：给你一个序列，然后让你找一个最长上升子序列，但是这个最长上升子序列的数在原来序列的间隔不少于d。
题解：如果没有d的要求就是一个求最长上升子序列。这里用线段树可以来优化。以数的值来建树。维护一个sum值，num[rt].sum表示以rt值结尾的最长上升子序列的长度。同时f[i]表示以第i个数结尾的最长上升子序列的长度。对于d，我们只要再算第i个数的时候，只更新了前1到i-d-1个数就行，然后查询0到a[i]-1之间最大值maxn，f[i]=maxn+1;如果a[i]=0,f[i]=1;
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int N=1e5+5; 7 int n,d; 8 int f[N]; 9 struct Node{10int l, r;11int sum;12inline int mid(){13 return (l+r)/2;14}15 }num[N*4];16 void pushup(int rt){17 num[rt].sum=max(num[rt<<1].sum,num[rt<<1|1].sum);18 }19 20 void build(int l,int r,int rt){21num[rt].l=l;22num[rt].r=r;23num[rt].sum=0;24if(l==r)return;25int mid=(l+r)/2;26build(l,mid,rt<<1);27build(mid+1,r,rt<<1|1);28 }29 void update(int pos,int rt,int val){30 if(num[rt].l==num[rt].r){31 num[rt].sum=val;32 return;33 }34int mid=num[rt].mid();35if(mid>=pos)update(pos,rt<<1,val);36else37 update(pos,rt<<1|1,val);38 pushup(rt);39 }40 int query(int l,int r,int rt){41if(num[rt].l==l&&num[rt].r==r){42 return num[rt].sum;43}44 int mid=num[rt].mid();45 if(mid>=r)return query(l,r,rt<<1);46 else if(mid<l)return query(l,r,rt<<1|1);47 else {48return max(query(l,mid,rt<<1),query(mid+1,r,rt<<1|1));49 }50 }51 int a[N],minn,ans;52 int main(){53 while(~scanf("%d%d",&n,&d)){54 minn=0,ans=0;55 memset(f,0,sizeof(f));56 for(int i=1;i<=n;i++){57scanf("%d",&a[i]);58minn=max(minn,a[i]);59 }60 build(0,minn,1);61 for(int i=1;i<=n;i++){62 if(i-d>1)update(a[i-d-1],1,f[i-d-1]);63 if(a[i]>0)f[i]=query(0,a[i]-1,1)+1;64 else65 f[i]=1;66 ans=max(ans,f[i]);67 }68 printf("%d\n",ans);69 }70 }
View Code
如果觉得《小明系列问题——小明序列》对你有帮助，请点赞、收藏，并留下你的观点哦！
