首页 > 代码库 > bzoj 3594: [Scoi2014]方伯伯的玉米田 dp树状数组优化

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

2024-07-31 00:26:19   211人阅读

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==6050000int 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==25000000int 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);}

 

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


联系
我们