HDU 5773 The All-purpose Zero（树状数组）

【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=5773

 

【题目大意】

　　给出一个非负整数序列，其中的0可以替换成任意整数，问替换后的最长严格上升序列长度。

【题解】

　　由于0的任意性，因此，最后的答案，将0全部选上，是最优的，因此我们只需知道在0之间可以插入几个其余的数，记s为0的前缀和，a为数列中的数，当两个数在这个答案序列中递增当且仅当ai-si>aj-sj。所以，我们用树状数组维护ai-si最长子序列，结果加上0的个数就是答案。

【代码】

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int base=100000,M=2000005;
int cnt,Cas=1,n,c[2000005],x,a[1000005],ans;
int add(int x,int num){while(x<M)c[x]=max(c[x],num),x+=x&-x;}
int sum(int x){int s=0;while(x>0)s=max(c[x],s),x-=x&-x;return s;}
int main(){
    scanf("%d",&n);
    while(~scanf("%d",&n)){
        memset(c,0,sizeof(c));
        for(int i=1;i<=n;i++){scanf("%d",&a[i]);}
        printf("Case #%d:",Cas++);ans=cnt=0;
        for(int i=1;i<=n;i++){
            if(a[i]==0){cnt++;continue;}
            a[i]=a[i]-cnt+base; 
            int t=sum(a[i]-1)+1;
            ans=max(ans,t);
            add(a[i],t);
        }printf(" %d
",ans+cnt);
    }return 0;
}