hdu5773 The All-purpose Zero 贪心+最长上升子序列

题目大意：可以将0替换成任意interger（包括负数），在此基础上求最长递增子序列。

解题思路：无疑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的个数则为答案。

#include<iostream>  
#include<cstdio>  
#include<cstring>  
#include<algorithm>  
#include<string>  
#include<vector>  
#include <ctime>  
#include<queue>  
#include<set>  
#include<map>  
#include<stack>  
#include<iomanip>  
#include<cmath>  
#include<bitset>  
#define mst(ss,b) memset((ss),(b),sizeof(ss))  
///#pragma comment(linker, "/STACK:102400000,102400000")  
typedef long long ll;  
#define INF (1ll<<60)-1  
#define Max 1e9  
using namespace std;  
int sum[100100];  
int a[100100],s[100100],vis[100100];  
int main(){  
    int T,n;  
    scanf("%d",&T);  
    for(int cas=1;cas<=T;cas++){  
        scanf("%d",&n);  
        mst(vis,0);  
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);  
        sum[0]=0;  
        for(int i=1;i<=n;i++) {  
            if(a[i]==0) sum[i]=sum[i-1]+1;  
            else sum[i]=sum[i-1];  
        }  
        for(int i=1;i<=n;i++) {  
            if(a[i]==0) {  
                vis[i]=1;  
                continue;  
            }  
            a[i]-=sum[i];  
        }  
        //for(int i=1;i<=n;i++) cout<<a[i]<<" ";cout<<endl;  
        int ans=sum[n];  
        int cnt=0;  
        s[0]=-1e9;  
        for(int i=1;i<=n;i++){  
            if(vis[i]==1) continue;  
            if(a[i]>s[cnt]) s[++cnt]=a[i];  
            else {  
                int x=lower_bound(s,s+cnt+1,a[i])-s;  
                s[x]=a[i];  
            }  
        }  
        //for(int i=0;i<=cnt;i++) cout<<s[i]<<" ";cout<<endl;  
        ans+=cnt;  
        printf("Case #%d: %d\n",cas,ans);  
    }  
    return 0;  
}