HDU-5772 贪心策略+LIS [2016多校]

给定大小为N的序列，当某个元素为0时，可将其替换成任意整数；问能够得到的最长递增子序列长度。

贪心策略基于这样一个性质：
最优子序列是包含了所有原来为0的元素的子序列。
证明可以用反证法，设一个最长子序列中不包含某个0元素，那么我们必然可以：

1. 用这个0元素替换它前面或者后面的已选非0元素，子序列长度不变；
2. 子序列增加这个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;
}