「SCOI2014」方伯伯的玉米田 解题报告

时间：2022-03-31 08:08:41

#2211. 「SCOI2014」方伯伯的玉米田

发现是取一个最长不下降子序列

我们一定可以把一个区间加的右端点放在取出的子序列的最右边，然后就可以dp了

\(dp_{i,j}\)代表前\(i\)个玉米田末尾为\(i\)拔高过\(j\)次的最大答案

\[dp_{i,j}=\max dp_{k,l}+1(k<i,h_i+j\ge h_k+l)
\]

发现可以维护的样子

维护一个\(f_{i,j}\)表示小于等于\(i\)高度(拔过后)拔的次数小于等于\(j\)次的最大值

直接二维树状数组搞就行了

Code

#include <cstdio>

#include <cstring>

int max(int x,int y){return x>y?x:y;}

int n,m,k,a[10010],f[6010][510];

int query(int x,int y)

{

    int ret=-(1<<30);

    for(int i=x;i;i-=i&-i)

        for(int j=y;j;j-=j&-j)

            ret=max(ret,f[i][j]);

    return ret;

}

void modify(int x,int y,int d)

{

    for(int i=x;i<=m;i+=i&-i)

        for(int j=y;j<=k;j+=j&-j)

            f[i][j]=max(f[i][j],d);

}

int main()

{

    scanf("%d%d",&n,&k);

    for(int i=1;i<=n;i++) scanf("%d",a+i),m=max(m,++a[i]);

    m+=++k;

    memset(f,-0x3f,sizeof f);

    modify(1,1,0);

    int ans=0;

    for(int i=1;i<=n;i++)

        for(int j=k-1;~j;j--)

        {

            int yuy=query(a[i]+j,j+1)+1;

            ans=max(ans,yuy);

            modify(a[i]+j,j+1,yuy);

        }

    printf("%d\n",ans);

    return 0;

}

2019.2.22

相关文章