BZOJ1175 : [Balkan2007]The stairways of Saharna

杨氏图表,维护若干个单调不下降队列。

每次新加入一个数时,先考虑第一个队列:

如果可以放在最后,则放在最后。

否则找到最小的可以替换的替换掉,再将替换的数放入第二个队列,以此类推。

最后$ans_i=\sum_{j=1}^i t_j$。

时间复杂度$O(n^2\log n)$。

#include<cstdio>
#define N 5005
int n,i,x,t[N];unsigned char q[N][N];
void up(int p,int x){
if(x>=q[p][t[p]]){q[p][++t[p]]=x;return;}
int l=1,r=t[p],mid,u;
while(l<=r)if(q[p][mid=(l+r)>>1]>x)r=(u=mid)-1;else l=mid+1;
up(p+1,q[p][u]),q[p][u]=x;
}
int main(){
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&x),up(1,x);
for(i=1;;i++){
printf("%d\n",t[i]+=t[i-1]);
if(t[i]==n)return 0;
}
}

  

上一篇:【Oracle教程资源大合集】Oracle数据库免费学习资源汇总


下一篇:直接拿来用!Facebook移动开源项目大合集