HDU 5773 The All-purpose Zero(树状数组)

发布时间:2017-1-23 12:35:45 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"HDU 5773 The All-purpose Zero(树状数组) ",主要涉及到HDU 5773 The All-purpose Zero(树状数组) 方面的内容,对于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\n",ans+cnt);
    }return 0;
}

上一篇:创建ASP.NET Core MVC应用程序(6)
下一篇:python3用BeautifulSoup用字典的方法抓取a标签内的数据

相关文章

相关评论