hdu4521小明系列问题——小明序列 (线段树+dp，求出不连续的最长升序子序列)
Problem DescriptionInputOutputSample InputSample OutputSource#include<stdio.h>#include<iostream>#include<algorithm>using namespace std;#define N 100000int tree[4*N];//记录在当前范围内那个点升序子序列最长int max(int a,int b){return a>b?a:b;}void builde(int l,int r,int k){ int m=(l+r)/2; tree[k]=0; if(l==r) return ; builde(l,m,k*2); builde(m+1,r,k*2+1);}void updata(int l,int r,int k,int id,int len){ if(l==r){ tree[k]=max(tree[k],len);//更新序列中有重复数或还没有更新的数的最长升序子序列长度 return ; } int m=(l+r)/2; if(id<=m) updata(l,m,k*2,id,len); else updata(m+1,r,k*2+1,id,len); tree[k]=max(tree[k*2],tree[k*2+1]);}int query(int l,int r,int k,int L,int R){ if(L<=l&&r<=R) return tree[k]; int m=(l+r)/2,len; if(R<=m) return query(l,m,k*2,L,R); else if(L>m) return query(m+1,r,k*2+1,L,R); else { len=query(l,m,k*2,L,R); len=max(len,query(m+1,r,k*2+1,L,R)); return len; }}int main(){ int lendp[N+5],m,n,d,ans[N+5],LIS; while(scanf("%d%d",&m,&d)>0) { n=0; for(int i=1;i<=m;i++) { scanf("%d",&ans[i]); ans[i]++; n=max(n,ans[i]); } builde(1,n,1); LIS=0; for(int i=1;i<=m;i++) { if(i-d-1>=1)//相隔d个数前面还有数 updata(1,n,1,ans[i-d-1],lendp[i-d-1]); lendp[i]=1;//本身算一个长度 if(ans[i]>1)//求出数ans[i]前面的LIS的长度 lendp[i]+=query(1,n,1,1,ans[i]-1); LIS=max(LIS,lendp[i]); } printf("%d\n",LIS); }}
