1109: [POI2007]堆积木Klo
stupid_lulu
posted @ 2013年3月21日 14:41
in poi
, 1653 阅读
树状数组维护序列,使{a[i]-i}不增,且{a[i]}递增。。。
#include<cstdio> #include<algorithm> using namespace std; const int maxi=~0u>>1; int n,ans(0); int f[200001],t[1000001]; struct re{ int n,h; }a[200001]; int lowbit(int x){return x&(-x);} bool cmp(re a,re b){return a.n==b.n? a.h<b.h:a.n>b.n;} void change(int x,int c){ while (x<=n){ t[x]=max(t[x],c); //printf("x=%d t[x]=%d\n",x,t[x]); x+=lowbit(x); } } int ques(int x){ int ans=0; while (x){ ans=max(ans,t[x]); //printf("%d t[x]=%d\n",x,t[x]); x-=lowbit(x); } //printf("ans=%d\n",ans); return ans; } int main(){ scanf("%d",&n); for (int i=1;i<=n;i++){ scanf("%d",&a[i].h); a[i].n=a[i].h-i; //printf("a[%d]=%d\n",i,a[i].n); } sort(a+1,a+n+1,cmp); for (int i=1;i<=n;i++){ //printf("i=%d n=%d h=%d\n",i,a[i].n,a[i].h); if (a[i].n>0) continue; int x; if (a[i].h-1>0){ //printf("%d\n",a[i].h); x=ques(a[i].h-1); }else x=0; //printf("x=%d\n",x); f[i]=x+1; //printf("f=%d\n",f[i]); ans=max(ans,f[i]); //printf("f[%d]=%d\n",i,f[i]); change(a[i].h,f[i]); } printf("%d\n",ans); }