题意：给出一个数列，其中0可以替换为任意整数，问最长严格递增子序列多长。
思路：如果某个数前面有0，那么这个0替换成该数-1为最优，那么我们就可以把数字-前面0的个数，去掉0形成一个新的数列，结果就是该数列的最长递增子序列+0的个数
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=1e5+10; 4 const int INF=1e9; 5 6 int a[N]; 7 int dp[N]; 8 9 int main(){ 10 int t; 11 int k=1; 12 scanf("%d",&t); 13 while(t--){ 14 int n; 15 scanf("%d",&n); 16 int l=0; 17 int Max=0; 18 int s=0; 19 int x; 20 for(int i=1;i<=n;i++) { 21 scanf("%d",&x); 22 if(x!=0) a[++l]=x-s; 23 else s++; 24 dp[i]=INF; 25 } 26 for(int i=1;i<=l;i++){ 27 int kk=lower_bound(dp+1,dp+1+l,a[i])-dp; 28 dp[kk]=a[i]; 29 Max=max(Max,kk); 30 } 31 printf("Case #%d: %d\n",k++,Max+s); 32 } 33 return 0; 34 } 35 /* 36 5 37 5 38 7 8 8 7 9 39 */
原文：http://www.cnblogs.com/hhxj/p/7119111.html