题意：题目含义简单，给定一个序列，求最大增加部分序列的长度，同时相邻两项的下标之差应大于d
分析：如果仅仅通过题意，加上最长的增加子串的限制条件，沿袭最长的增加子串的想法，则DP[I]=max[I]，dp[j] 1(，(i - j d a[i] a[j] ) )
从状态转移方程式可知，问题的关键是维护区间(0，i - d - 1 )的最大的dp值，对应值小于a(I )
换句话说，如果以a[i]值作为下标，保证当前区间[0，a[I]-1]的dp值全部满足[I-jd]，则dp[i]等于区间[0，a[I]-1]的最大值
hdu 4521 # include iostream # include algorithm # include stdio.h # include string.h # include stdlib.husingnamespacestd； const int N=100000 10； struct node{ int l，r，max； }p[N * 3]； int a[N]，d，n； int dp[N]； voidbuild(ints，int t，int k ) { p[k].l=s； p[k].r=t； p[k].max=0； if(s==t ) return； intmid=(ST ) 1，kl=k 1，kr=kl 1； Build(s，mid，kl )； build(mid1，t，kr )； }voidinsert(intk，int s，int val ) if ) p[k].l==p[k].rp[k].l==s ) p[k].max=max ) p[k].k 返回； (intmid=) p[k].Lp[k].r ) 1，kl=k 1，kr=kl 1； if(s=mid ) insert(KL，s，val )； Elseinsert(kr，s，val )； p[k].max=max(p[KL].max，p[kr].max )； (intquery ) intk，int s，int t ) if ) s=p[k].lt=p[k].r ) { return p[k].max； (intmid=) p[k].Lp[k].r ) 1，kl=k 1，kr=kl 1； int a=0，b=0； if(s=mid ) a=query ) KL，s，t )； if(tmid ) b=query(kr，s，t )； returnmax(a，b )； (}int main ) ) while ) Scanf(%d%d )，n，d )==2) { int maxa=0； for(intI=1； i=n； I ) Scanf('%d '，a i )； a[i]； maxa=max(maxa，a[i]； }memset(DP，0，sizeof ) DP )； Build(0，maxa，1 )； int ans=1； for(intI=1； i=n； I ) int tmp=query (1，0，a[i] - 1 )； DP[I]=max(DP[I]，tmp 1)； ans=max(ans，dp[i] )； if(I-d0 ) insert(1) 1、a[i - d]、dp[i - d]； //将下标满足的DP值(printf )“%dn”，ans )插入段树中； } return 0； }
转载于：https://www.cn blogs.com/nanke/archive/2013/04/01/2994358.html