自动搬运

查看原文

来自洛谷，原作者为

	Forever丶CIL **

搬运于2025-08-24 21:47:50，当前版本为作者最后更新于2017-08-11 09:53:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P3335 这个题思维难度还是有的。。(至少我是这么想的。。大佬就别吐槽我了)

首先，通过题目描述，我们可以在纸上画一画，可以发现，图像一定是像长城一样的

就是好多个矩形它们的底在一条直线上，高和宽不同，而且，还有一点就是它是高低相间的

而且由右转形成高峰，由左转形成低谷。

那么我们可以枚举图的右下角(i,j)，那么有两种情况：

一:第j-1列和第j列在同一个矩形里；

二:第j-1列和第j列在不同的矩形里；

我们要记录的状态与点(i,j),p(指的是当前枚举的是第p个矩形),h(当前枚举的举行高度为i-h+1)有关

对于一情况：令f[i][j][p][h]来表示前i行前j列，到第p个矩形，且第p个矩形高为i-h+1时的最优解。 则 f[i][j][p][h]=f[i][j-1][p][h]+s[i][j]-s[h-1][j];

（这里这个s数组求的是每一列的前缀和，可以在输入中预处理出来，方便计算用）

对于二情况：再分两种讨论，如果第p个矩形比第p-1个矩形高，则应从f[i][j-1][p-1][高度小于i-h+1]中找一个 max来转移，如果第p个矩形比第p-1个矩形矮，则应从f[i][j-1][p-1][高度大于i-h+1]中找一个max来转移。 因为一个个枚举高度大于i-h+1和小于i-h+1太浪费时间了，所以我们再开一个数组g[i][j][p][h][0/1]来表示 高度比i-h+1高的/矮的之中，f数组中的max。

我这里直接用f[i][j-1][p-1][高度大于i-h+1]这样的方式讲解了，但其实f数组最后一维的h并不是第p个矩形的高度，而是这样的：i是矩形的最下面一行，h则是最上面一行，所以i-h+1才是高度。

根据分析，转移就好写了：

f[i][j][p][h]=max(f[i][j-1][p][h],g[i][j-1][p-1][h][p%2])+s[i][j]-s[h-1][j];

关于g数组的维护，因为我们已经维护出f数组的第j列了

那么这一列所在的矩形要么是低谷，要么是高峰，我们都要考虑

->高峰：

g[i][j][p][h][0]=max(f[i][j][p][h-1],g[i][j][p][h-1][0]);

->低谷：

g[i][j][p][h][1]=max(f[i][j][p][h+1],g[i][j][p][h+1][1]);

当然我们可以在计算过程中更新答案，还可以省掉i这一维

因为从方程中就可以看出来i其实没有参与转移

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=120;
const int Inf=1000000001; 
int n,m,k,ans;
int a[maxn][maxn];
int f[maxn][25][maxn];
int g[maxn][25][maxn][2];
int s[maxn][maxn];
void ini()
{
	scanf("%d%d%d",&n,&m,&k);
	k=k*2+1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&a[i][j]); s[i][j]=s[i-1][j]+a[i][j];
	for(int p=1;p<=k;p++)
		for(int h=1;h<=n;h++)
			f[0][p][h]=-Inf,g[0][p][h][0]=-Inf,g[0][p][h][1]=-Inf;
}
void dp()
{
	ans=-Inf;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			for(int p=1;p<=k;p++)
			{
				for(int h=i;h>=1;h--)
					f[j][p][h]=max(f[j-1][p][h],g[j-1][p-1][h][p%2])+s[i][j]-s[h-1][j];
				g[j][p][1][0]=-Inf;
				for(int h=2;h<=i;h++) g[j][p][h][0]=max(f[j][p][h-1],g[j][p][h-1][0]);
				g[j][p][i][1]=-Inf;
				for(int h=i-1;h>=1;h--) g[j][p][h][1]=max(f[j][p][h+1],g[j][p][h+1][1]);
			}
			ans=max(ans,max(f[j][k][i],g[j][k][i][0]));
		}
	}
}
int main()
{ 
	ini();
	dp();
	printf("%d\n",ans);
	return 0;
}

大家也会发现，g数组的最后一维也能省掉，因为对于特定的p，它是高峰还是低谷是确定的。

rp++