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
",ans);
}