题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5773
0可以改变成任何数，问你严格递增的子序列最长是多少。
猜测0一定在最长上升子序列中用到，比如2 0 0 3 5 6，可以变为2 3 4 3 5 6。
那我们先算出0的个数，然后每次遇到0就把后面一开始不是0的-1，算出剩下数的最长上升子序列(nlogn)，然后加上0的个数。
1 //#pragma comment(linker, "/STACK:102400000, 102400000") 2 #include <algorithm> 3 #include <iostream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <ctime> 10 #include <list> 11 #include <set> 12 #include <map> 13 using namespace std; 14 typedef long long LL; 15 typedef pair <int, int> P; 16 const int N = 1e5 + 5; 17 int inf = 0x3f3f3f3f; 18 int a[N], dp[N], b[N]; // dp[i]:长度为i的上升子序列中最后元素的最小值 19 20 int main() 21 { 22 int t, n; 23 scanf("%d", &t); 24 for(int ca = 1; ca <= t; ++ca) { 25 scanf("%d", &n); 26 int dec = 0, index = 0; 27 for(int i = 1; i <= n; ++i) { 28 scanf("%d", a + i); 29 if(a[i] == 0) { 30 ++dec; 31 } else { 32 a[i] -= dec; 33 b[++index] = a[i]; 34 } 35 dp[i] = inf; 36 } 37 for(int i = 1; i <= index; ++i) { 38 *lower_bound(dp + 1, dp + index + 1, b[i]) = b[i]; 39 } 40 printf("Case #%d: %d\n", ca, lower_bound(dp + 1, dp + n + 1, inf) - dp - 1 + dec); 41 } 42 return 0; 43 }