bzoj 3594: [Scoi2014]方伯伯的玉米田 dp树状数组优化

3594: [Scoi2014]方伯伯的玉米田

Time Limit: 60 Sec  Memory Limit: 128 MB
Submit: 314  Solved: 132
[Submit][Status]

Description

方伯伯在自己的农田边散步,他突然发现田里的一排玉米非常的不美。
这排玉米一共有N株,它们的高度参差不齐。
方伯伯认为单调不下降序列很美,所以他决定先把一些玉米拔高,再把破坏美感的玉米拔除掉,使得剩下的玉米的高度构成一个单调不下降序列。
方伯伯可以选择一个区间,把这个区间的玉米全部拔高1单位高度,他可以进行最多K次这样的操作。拔玉米则可以随意选择一个集合的玉米拔掉。
问能最多剩多少株玉米,来构成一排美丽的玉米。

Input


第1行包含2个整数n,K,分别表示这排玉米的数目以及最多可进行多少次操作。
第2行包含n个整数,第i个数表示这排玉米,从左到右第i株玉米的高度ai。

Output


输出1个整数,最多剩下的玉米数。

Sample Input

3 1
2 1 3

Sample Output

3

HINT

 

1 < N < 10000,1 < K ≤ 500,1 ≤ ai ≤5000

 

 

  想当年这道题在考场上居然没有想到是DP,当时太naive了。不过现在做这道题还是有些费劲,原因是我最开始的DP方程有问题,调了很久,实在忍无可忍,找hja要了标程拍了几组数据就过了。

  dp方程,dp[i][j]表示到第i颗玉米,用了j次提升,最多保留多少:

    dp[i][j]=dp[k][j]+1(k<=i && a[k]<=a[i)

    dp[i][j]=dp[k][j+a[i]-a[k]]+1 (j<=i && a[k]<=a[i])

  第一个方程可以很快看出用树状数组维护,而第二个方程要稍微转一下弯,由于如果j+a[i]是恒定的,那么dp[j+a[i]-a[k]]的取值范围大致相同,我们树状数组可以维护相同j+a[i]下dp[][]取值。

  注意这道题不能自己乱想dp方程,最开始我写的方程还有dp[i][j]=dp[k][j] (k<=i),这样的状态转移有缺陷,改过以后我的ans又只在dp[n][i]取最值,这个错误非常隐蔽,需要在编的时候注意。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#ifdef ONLINE_JUDGE
#define MAXN 11000
#define MAXV 5100
#define MAXK 550
#define VAL1 MAXV-2
#else
#define MAXN 1010
#define MAXV 510
#define MAXK 53
#define VAL1 MAXV-2
#endif
#define INF 0x3f3f3f3f
#define deal(x,y) if ((x)<(y))(x)=(y);
int dp[MAXK];//11000*550==6050000
int a[MAXN];
void Add_val(int *tarr,int pos,int val,int ll)
{
        pos++;
        while (pos<ll)
        {
                tarr[pos]=max(tarr[pos],val);
                pos+=pos&(-pos);
        }
}
int Qry_val(int *tarr,int pos)
{
        pos++;
        int res=-INF;
        while (pos)
        {
                res=max(res,tarr[pos]);
                pos-=pos&(-pos);
        }
        return res;
}
int g1[MAXK][MAXV];
int g2[MAXK+MAXV][MAXV];//5600*5100==25000000
int main()
{
        freopen("input.txt","r",stdin);
        int n,m;
        int i,j,k;
        scanf("%d%d",&n,&m);
        a[0]=0;
        for (i=1;i<=n;i++)
                scanf("%d",a+i);
        for (j=0;j<=m;j++)
                dp[j]=-INF;
        for (i=0;i<=m;i++)
                for (j=0;j<MAXV;j++)
                        g1[i][j]=-INF;
        for (i=0;i<=m+MAXV;i++)
                for (j=0;j<MAXV;j++)
                        g2[i][j]=-INF;
        int ans=-INF;
        dp[0]=0;
        Add_val(g1[0],a[0],dp[0],MAXV);
        Add_val(g2[0+a[0]],VAL1-a[0],dp[0],MAXV);
        for (i=1;i<=n;i++)//10000
        {
                for (j=0;j<=m;j++)//500
                {
                        /*for (k=0;k<i;k++)//10000
                        {
                                if (a[i]>=a[k])
                                {
                                        deal(dp[i][j],dp[k][j]+1);
                                }else
                                {
                                        if (j-(a[k]-a[i])>=0)
                                                deal(dp[i][j],dp[k][j-(a[k]-a[i])]+1);
                                        deal(dp[i][j],dp[k][j]);
                                }
                        }*/    
                        //dp[i][j]=dp[k][j]+1(k<=i && a[k]<=a[i)
                        //dp[i][j]=dp[k][j+a[i]-a[k]]+1 (j<=i && a[k]<=a[i])
                        dp[j]=-INF;
                        dp[j]=max(dp[j],Qry_val(g1[j],a[i])+1);
                        dp[j]=max(dp[j],Qry_val(g2[j+a[i]],VAL1-a[i])+1);

                        Add_val(g1[j],a[i],dp[j],MAXV);
                        Add_val(g2[a[i]+j],VAL1-a[i],dp[j],MAXV);
                        deal(ans,dp[j]);
                }
        }
        printf("%d\n",ans);
}

 

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。