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;
}
评论 (0)
