BZOJ-1109: [POI2007]堆积木Klo

[文章目录]

Description

Mary在她的生日礼物中有一些积木。那些积木都是相同大小的立方体。每个积木上面都有一个数。Mary用他的所有积木垒了一个高塔。妈妈告诉Mary游戏的目的是建一个塔,使得最多的积木在正确的位置。一个上面写有数i的积木的正确位置是这个塔从下往上数第i个位置。Mary决定从现有的高塔中移走一些,使得有最多的积木在正确的位置。请你告诉Mary她应该移走哪些积木。1<=n<=100000,1<=ai<=1000000

i位置满足并且上一个满足位置是j满足条件的情况:i-j>=a[i]-a[j] i>j a[i]>a[j] 中间的发现可以省略,所以就是一个二维偏序,注意判断一下i>a[i]

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,ans;
struct node
{
    int w,b;
}a[101000];
bool cmp(node x,node y) {
    return x.b==y.b?x.w<y.w:x.b<y.b;
}
int f[1001000];
int query(int x){int re=0; while(x>0) re=max(re,f[x]),x-=-x&x; return re;}
void fix(int x,int y) {while(x<=1000000) f[x]=max(f[x],y),x+=-x&x;}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i].w);
        a[i].b=i-a[i].w;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;++i)
    {
        if(a[i].b>=0)
        {
            int tmp=query(a[i].w-1);
            tmp++; fix(a[i].w,tmp);
            ans=max(ans,tmp);
        }
    }
    printf("%d",ans);
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注