给定大小为N的序列，当某个元素为0时，可将其替换成任意整数；问能够得到的最长递增子序列长度。
贪心策略基于这样一个性质：
最优子序列是包含了所有原来为0的元素的子序列。
证明可以用反证法，设一个最长子序列中不包含某个0元素，那么我们必然可以：
- 用这个0元素替换它前面或者后面的已选非0元素，子序列长度不变；
- 子序列增加这个0元素，子序列长度变长；
无论如何都不会比原来的差。
所以A[i], A[j] (i<j) 选为子序列中连续元素的条件是：他们的差值必须大于其之间的0元素个数。
即：A[j]-A[i]>SUM[j]-SUM[i] (SUM[i]表示i号元素之前有多少个0元素)
转化一下即是：A[j]-SUM[j]>A[i]-SUM[i]
由以上这个式子，我们可以直接将所有A[i]修改为A[i]-SUM[i]之后，直接计算非0元素的LIS长度并加上0元素个数即可，非常妙。
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
#define N 1050
int d[N];
int main(){
int t,kase=0;
cin>>t;
while(t--){
int n,zeros=0;
cin>>n;
vector<int> a;
for (int i=0;i<n;i++){
int x;
cin>>x;
if (x) a.push_back(x-zeros);
else zeros++;
}
int cnt = 0;
for (int i=0;i<a.size();i++){
if (!cnt || a[i]>d[cnt-1]) d[cnt++] = a[i];
int pos = lower_bound(d, d+cnt, a[i]) - d;
d[pos] = a[i];
}
printf("Case #%d: %d\n", ++kase, cnt+zeros);
}
return 0;
}
