DP的优化

andyl / 2023-07-17 / 原文

P3287 [SCOI2014] 方伯伯的玉米田

首先容易分析出一个性质：拔高玉米时，拔高 \([i,n]\) 区间的玉米一定是最优的。然后就有了一个暴力DP：

设 \(f[i][j]\) 表示对于前 \(i\) 个玉米（第 \(i\) 个玉米保留），拔高 \(j\) 次最多能保留多少玉米。

状态转移方程：

\(if(a[l]>a[i]\&\&a[l]-a[i]<=j):f[i][j]=max(f[l][j-(a[l]-a[i])])+1\)

\(if(a[l]<a[i]):f[i][j]=max(f[l][j])+1\)

~~然后你就可以拿到10分的好成绩~~

考虑优化。我们发现，状态转移需要求二维前缀的最大值，所以考虑二维树状数组优化。然而， \(a[l]-a[i]<=j\) 导致不能直接转移，所以有必要重新考虑状态，使得转移没有条件限制。

设 \(dp[i][j][k]\) 表示对于前 \(i\) 个玉米（第 \(i\) 个玉米保留），拔高 \(j\) 次，第 \(i\) 个玉米高度为 \(k\) 时，最多能保留多少玉米。

状态转移方程：\(dp[i][j][a[i]+j]=max(dp[i-1][p][q]),1<=p<=j,1<=q<=a[i]+j\)

然后就可以愉快地使用二维树状数组了。

\(code:\)

#include<iostream>
#include<cstdio>
using namespace std;
int n,k,maxn,now[50005],a[500005],dp[505][5505],ans;
int ask(int x,int y){
	int re=0;
	for(int i=x;i;i-=i&(-i))
		for(int j=y;j;j-=j&(-j))
			re=max(re,dp[i][j]);
	return re;
}
void add(int x,int y,int z){
	for(int i=x;i<=k+1;i+=i&(-i))
		for(int j=y;j<=k+maxn;j+=j&(-j))
			dp[i][j]=max(dp[i][j],z);
}
int main(){
	//freopen("1.in","r",stdin);
	//freopen("1.out","w",stdout);
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i)
		scanf("%d",&a[i]),maxn=max(maxn,a[i]);
	for(int i=1;i<=n;++i){
		for(int j=0;j<=k;++j){
			int t=ask(j+1,a[i]+j)+1;//这里写j+1是避免j==0时树状数组死循环 
			now[j]=t;
			ans=max(ans,t);
		}
		for(int j=0;j<=k;++j)
			add(j+1,a[i]+j,now[j]);
	}
	/*for(int i=1;i<=n;++i)//注释掉的部分是暴力DP 
		for(int j=0;j<=k;++j){
			for(int l=0;l<i;++l){
				if(a[l]>a[i]&&a[l]-a[i]<=j)
					dp[i][j]=max(dp[i][j],dp[l][j-(a[l]-a[i])]+1);
				else if(a[l]<=a[i])
					dp[i][j]=max(dp[i][j],dp[l][j]+1); 
			}*/
	printf("%d\n",ans);
	return 0;
}