题目地址:点我
题意:给你一个序列,找出最大上升子序列的长度,其中序列中的0可以变为任意整数(正负都可以)。
解法:无疑LIS,将所有的0全部提取出来,求出此时序列的LIS(不含0的),这是针对0在子序列的外面的情况,如0,1,2,3,0.那么如果0在子序列中间怎么办?很简单,把读入的非0的数的值减去这个数前面0的个数即可,如1,2,0,3,4。在提取出0后序列其实为1,2,2,3,LIS的长度为3,加上0的个数则为答案。感觉这个贪心的思路很赞。dp求lis是经典题了。

#include <bits/stdc++.h>
using namespace std;
int ks = 0, T, n, a[100005];

int main(){
    scanf("%d", &T);
    while(T--){
        memset(a, 0, sizeof(a));
        int m = 0;
        int tot = 0;
        scanf("%d", &n);
        for(int i = 0; i < n; i++){
            int x;
            scanf("%d", &x);
            if(x == 0) tot++;
            else{
                x -= tot;
                int p = lower_bound(a, a + m, x) - a;
                a[p] = x;
                m = max(m, p + 1);
            }
        }
        printf("Case #%d: %d\n", ++ks, m + tot);
    }
    return 0;
}