自动搬运

查看原文

来自洛谷，原作者为

	WaltVBAlston Always continue; Never break;

搬运于2025-08-24 22:18:33，当前版本为作者最后更新于2020-03-16 15:09:57，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

日常刷新题，维护自己在小伙伴们中的微信。

这道题的题意很明显，连动态转移方程都给你了：

dp[j][i]=max(dp[j-1][i-1],max(dp[j+1][i-1],dp[j][i-1]))+a[j][i];

感觉莫名很像一道叫做：红牌 的题目。

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,m;
int dp[1001][1001];
int a[1001][1001];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			scanf("%d",&a[i][j]);
		}
	}
	dp[1][1]=a[1][1];
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			dp[j][i]=max(dp[j-1][i-1],max(dp[j+1][i-1],dp[j][i-1]))+a[j][i];
		}
	} 
	printf("%d",dp[n][m]);
	return 0;
}

慢着，如果你直接把这份代码交上去等待着你的 （我相信你不会那么干的）那么等待着你的就是：WAWAWAWAWA。没错，五个点。

到底是为什么呢？

我们来分析一下：把这张地图看成一个四边形，那么我们可以发现，左上点（起点），到右下点（终点），它们练成的斜线以下的部分，是到达不了的（读题就很容易看出）。

所以我们在for的边界应该是这样的：

j<=i&&j<=n;

AC代码如下：

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,m;
int dp[1001][1001];
int a[1001][1001];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			scanf("%d",&a[i][j]);
		}
	}
	dp[1][1]=a[1][1];
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n&&j<=i;j++)
		{
			dp[j][i]=max(dp[j-1][i-1],max(dp[j+1][i-1],dp[j][i-1]))+a[j][i];
		}
	} 
	printf("%d",dp[n][m]);
	return 0;
}

记得一定要先枚举列，再枚举行！

（第一篇题解，大家多多资瓷）