BZOJ 3594 [Scoi2014]方伯伯的玉米田动态规划+二维树状数组

本文主要是介绍BZOJ 3594 [Scoi2014]方伯伯的玉米田动态规划+二维树状数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

HINT

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

传送门

一开始不太会= =然后百度了一下发现有个结论：

每次选择一个区间增加，这个区间的右端点一定是n。

……woc这很有道理啊。。。

dp[i][j]表示前i个玉米地，使用了j次机会的最多个数。

容易知道dp[i][j]=max{dp[x][y]}+1，

其中，要满足a[x]+y<=a[i]+j

然后就可以得到一个O((NK)^2)的算法了……boom。。

利用二维树状数组，对(a[i]+j,j)进行优化，

因为显然dp[x][y]满足的条件一个是a的条件，还有一个就是y<j，

x是1~n过来的，不用管。

注意j的枚举是要倒序的，

虽然一开始正序的某种写法也不是很清楚为什么错，

后来听大佬们“联想01背包”

……

好吧。。

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}
const int N=10005,KK=505,AMAX=5005;
int n,K,maxa;
int a[N],f[N][KK];
int tr[AMAX+KK][KK];
void add(int x,int y,int z){for (;x<=maxa+K;x+=x&-x)for (int p=y;p<=K;p+=p&-p) tr[x][p]=max(tr[x][p],z);
}
int query(int x,int y){int z=0;for (;x;x-=x&-x)for (int p=y;p;p-=p&-p) z=max(z,tr[x][p]);return z;
}
int main(){n=read(),K=read()+1; maxa=0;for (int i=1;i<=n;i++)a[i]=read(),maxa=max(maxa,a[i]);for (int i=1;i<=K;i++) f[1][i]=1,add(a[1]+i,i,1);int ans=0;for (int i=2;i<=n;i++)for (int j=K;j;j--)f[i][j]=query(a[i]+j,j)+1,ans=max(ans,f[i][j]),add(a[i]+j,j,f[i][j]);printf("%d\n",ans);return 0;
}

这篇关于BZOJ 3594 [Scoi2014]方伯伯的玉米田动态规划+二维树状数组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！