1551: LongestIncreasingSubsequence AgainTime Limit:2 SecMemory Limit:256 MBSubmit:29Solved:15[Submit][Status][Web Board]Description
Give you a numeric sequence. If you can demolish arbitrary amount of numbers, what is the length of the longest increasing sequence, which is made up of consecutive numbers? It sounds like LongestIncreasingSubsequence at first sight. So, there is another limitation: the numbers you deleted must be consecutive.
Input
There are several test cases.For each test case, the first line of input contains the length of sequence N(1≤N≤10^4). The second line contains the elements of sequence——N positive integers not larger than 10^4.
Output
For each the case, output one integer per line, denoting the length of the longest increasing sequence of consecutive numbers, which is achievable by demolishing some(may be zero) consecutive numbers.
Sample Input71 7 3 5 9 4 862 3 100 4 4 5Sample Output44HINTSource#include<stdio.h>#include<algorithm>using namespace std;const int N = 10005;struct qj{int l,r;}kuai[N];int b[N],tn,n,a[N],k[N],tree[N*4];void builde(int l,int r,int e){int m=(l+r)/2;tree[e]=0;if(l==r)return ;builde(l,m,e*2);builde(m+1,r,e*2+1);}void settree(int l,int r,int e,int id,int ans){int m=(l+r)/2;if(tree[e]<ans)tree[e]=ans;if(l==r){return ;}if(id<=m)settree(l,m,e*2,id,ans);elsesettree(m+1,r,e*2+1,id,ans);}int findans(int l,int r,int e,int id){int m=(l+r)/2,ans=0;if(l==r)return 0;if(id<=m){ans=findans(l,m,e*2,id);if(ans<tree[e*2+1])ans=tree[e*2+1];return ans;}elsereturn findans(m+1,r,e*2+1,id);}int cmp(int aa,int bb){return aa<bb;}void cut(){tn=1;sort(b+1,b+1+n,cmp);for(int i=2;i<=n;i++)if(b[i]!=b[tn])b[++tn]=b[i];}int two(int aa){int l,r,m;l=1;r=tn;while(l<=r){m=(l+r)/2;if(b[m]==aa)return m;if(b[m]>aa)r=m-1;else l=m+1;}return m;}int main(){while(scanf("%d",&n)>0){if(n==0){printf("0\n");continue;}for(int i=1;i<=n;i++){scanf("%d",&a[i]);b[i]=a[i];}cut();builde(1,tn,1);int m=1;kuai[m].l=kuai[m].r=1;for(int i=2;i<=n;i++)if(a[kuai[m].r]>=a[i]){m++; kuai[m].l=kuai[m].r=i;}elsekuai[m].r++;for(int i=1;i<=m;i++){for(int j=kuai[i].r;j>=kuai[i].l;j–)k[j]=kuai[i].r-j+1;}int ans=0;for(int i=m;i>0;i–){int aaa,id;for(int j=kuai[i].r;j>=kuai[i].l;j–){id=two(a[j]);aaa=j-kuai[i].l+1;aaa+=findans(1,tn,1,id);if(ans<aaa)ans=aaa;}for(int j=kuai[i].r;j>=kuai[i].l;j–){id=two(a[j]);settree(1,tn,1,id,k[j]);}}printf("%d\n",ans);}}
，知已知彼，百战百胜。
