自动搬运

查看原文

来自洛谷，原作者为

	SunsetVoice **

搬运于2025-08-24 21:36:03，当前版本为作者最后更新于2023-04-01 21:03:13，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

更好的阅读体验~

原题传送门~

本题解概要：

1. 为什么需要多加一维存储方向
2. 三维 dp 思路（包括 dp 五步）
3. code&注意事项

最后更新：修改了标点和英文，中文间的空格。鸣谢 @dyc2022 。

1.为什么要多加一维用来存储方向？

二维的正常转移式：

$$dp_{i,j} = \min(dp_{i,j-1}+a_{i-1,j},dp_{i-1,j}+a_{i,j-1})+a_{i,j+1}+a_{i+1_j} $$

放在代码中即为：

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

但是此时如果途中方案有转弯（比如从 $a_{i-1,j-1}$ 走到 $a_{i-1,j}$ 再走到 $a_{i,j}$）（下图）

→	↓
	↓

则 $a_{i,j-1}$ 会被计算两次。 诸如此类的，在不思考方向的时候将很难判重。

所以，解决方案是增加一维，变为三维记录值。

（血的教训:亲测只用二维数组只能 50 pts）

2. 三维 dp 思路（dp 五步）

状态表示：

设 $dp_{i,j,0}$ 表示在考虑前 $i$ 行前 $j$ 列且上一步从左边走过来时的最小害怕值， $dp_{i,j,1}$ 表示在考虑前 $i$ 行前 $j$ 列且上一步从上面走过来时的最小害怕值。

阶段划分

逐行逐列完成 dp 数组。不用说了吧

求解目标

根据状态表示可以得出，$\min(dp_{n,m,0},dp_{n,m,1})$ 即为答案。

状态转移（敲黑板）

温馨提示：建议读者们跟着草稿纸一起画一边图，以便真正理解 dp。

本处将当前格子设为 $a_{i,j}$。

先说说倒数第一步从上面转移过来的情况：

此时倒数第二步分两种：一种是上一格是从左边转移过来的，即：从 $a_{i-1,j-1}$ 转移（走）到 $a_{i-1,j}$ 再走（转移）到 $a_{i,j}$ 中的。

那么，这种情况下，$dp_{i-1,j-1}$ （ 01 都行 ）显然至少包括了上下左右中五个格子，即 $dp_{i-1,j-1}$ 至少包括了 $a_{i-2,j-1},a_{i-1,j-2},a_{i-1,j-1},a_{i,j-1}$ 以及 $a_{i-1,j}$ 这五个格子中的老鼠数目。而 $dp_{i-1,j,0}$ 不仅至少包括了前面所说的五个数，还至少额外添加了 $a_{i,j},a_{i-1,j+1}$ 以及 $a_{i-2,j}$ 这三个格子中的老鼠数目。

汇总一下，在从 $a_{i-1,j-1}$ 转移（走）到 $a_{i-1,j}$ 再走（转移）到 $a_{i,j}$ 的情况下， $dp_{i-1,j,0}$ 至少包括了 $a_{i-2,j-1},a_{i-1,j-2},a_{i-1,j-1},a_{i,j-1},a_{i-1,j},a_{i,j},a_{i-1,j+1}$ 以及 $a_{i-2,j}$ 这几个格子之中的老鼠总数目。

有些头晕？画一个表格或是平面直角坐标系对着看一看吧。

继续，我们发现原来需要考虑五格(上下左右中)的 $dp_{i,j}$ 这个格子现在继承一下 $dp_{i-1,j,0}$ 就等于继承了至少 3 格（ $a_{i-1,j},a_{i,j},a_{i,j-1}$），所以，$dp_{i,j,1} = dp_{i-1,j,0}+$ 剩下两格 $a_{i+1,j}+a_{i,j+1}$。

呼！第一种情况总结完了，第二种呢？

第二种情况是从 $a_{i-2,j}$ 转移（走）到 $a_{i-1,j}$ 再转移（走）到 $a_{i,j}$ 中。

但，与之不同的是，$dp_{i-1,j,1}$ 并不包括 $a_{i,j-1}$。

想一想，为什么？

继续，我们发现原来需要考虑 5 格(上下左右中)的 $dp_{i,j}$ 这个格子现在继承一下 $dp_{i-1,j,1}$ 就等于继承了 2 格（$a_{i-1,j},a_{i,j}$)，所以，$dp_{i,j,1} = dp_{i-1,j,0}+$ 剩下两格 $a_{i+1,j}+a_{i,j+1}$。

所以，$dp_{i,j,1} = dp_{i-1,j,1}+$ 剩下 3 格 $a_{i+1,j}+a_{i,j+1}+a_{i,j-1}$。

最后一步了！我们把以上两种情况汇总一下就得到了以下方程式：

$$dp_{i,j,1} = \min(dp_{i-1,j,0}+a_{i+1,j}+a_{i,j+1},dp_{i-1,j,1}+a_{i,j-1}+a_{i+1,j}+a_{i,j+1}) $$

再稍微简化一下：

$$dp_{i,j,1} = \min(dp_{i-1,j,0},dp_{i-1,j,1}+a_{i,j-1})+a_{i+1,j}+a_{i,j+1} $$

呼！恭喜恭喜！你已经推完了倒数第一部向下的情况了！

所以接下来倒数第一步向右走的情况就不需要我再说了吧？

什么？你还蒙圈？

好的，再说说倒数第一步从左面转移过来的情况：

其实倒数第一步向右走的情况也分两种（倒数第二步向下或向右），而且推导方法和上面极为相似。好的，继续。

第一种：向右再向下。

即：从 $a_{i-1,j-1}$ 转移（走）到 $a_{i,j-1}$ 再走（转移）到 $a_{i,j}$ 中。

此时 $dp_{i,j-1,1}$ 已经覆盖了 $a_{i,j},a_{i,j-1},a_{i+1,j}$ 这 3 个位置的数。 所以，第一种情况中， $dp_{i,j,0} = dp_{i,j-1,0}+a_{i+1,j}+a_{i,j+1}$。

第二种：向右再向右。

即：从 $a_{i,j-2}$ 转移（走）到 $a_{i,j-1}$ 再走（转移）到 $a_{i,j}$ 中。

此时 $dp_{i,j-1,0}$ 已经覆盖了 $a_{i,j},a_{i,j-1}$ 这两个位置的数。 所以，第二种情况中， $dp_{i,j,0} = dp_{i,j-1,0}+a_{i-1,j}+a_{i+1,j}+a_{i,j+1}$。

又是最后一步了！把以上两种情况汇总一下就得到了以下方程式：

$$dp_{i,j,0} = \min(dp_{i,j-1,1},dp_{i,j-1,0}+a_{i-1,j})+a_{i+1,j}+a_{i,j+1} $$

好了，第二种情况也讨论完了！把以上两个方程式整合一下然后隆重推出-----------------

$$dp_{i,j,0} = \min(dp_{i,j-1,1},dp_{i,j-1,0}+a_{i-1,j})+a_{i+1,j}+a_{i,j+1} $$$$dp_{i,j,1} = \min(dp_{i-1,j,0},dp_{i-1,j,1}+a_{i,j-1})+a_{i+1,j}+a_{i,j+1} $$

初始状态/边界条件

特殊的，

$$dp_{1,1,0} = a_{1,1}+a_{1,2}+a_{2,1}$$ $$dp_{1,1,1} = a_{1,1}+a_{1,2}+a_{2,1}$$

3.code&注意事项：

请注意：初始值最好赋值成正无穷。

code：

OK，接下来就是喜闻乐见的代码时间！

ACcode：

#include<bits/stdc++.h>
using namespace std;
int main(){
	long long i,j,n,m,dp[1002][1002][3] = {0},a[1002][1002] = {0};
	cin>>n>>m;
	for(i = 1;i<=n;i++){
		for(j = 1;j<=m;j++){
			cin>>a[i][j];
			dp[i][j][0] = 999999999;
			dp[i][j][1] = 999999999;
		}
	}
	dp[1][1][0] = a[1][1]+a[1][2]+a[2][1];
	dp[1][1][1] = a[1][1]+a[1][2]+a[2][1];
	for(i = 2;i<=m;i++)dp[1][i][0] = dp[1][i-1][0]+a[1][i+1]+a[2][i];
	for(i = 2;i<=n;i++)dp[i][1][1] = dp[i-1][1][1]+a[i+1][1]+a[i][2];
	for(i = 2;i<=n;i++){
		for(j = 2;j<=m;j++){
			dp[i][j][1] = min(dp[i-1][j][0],dp[i-1][j][1]+a[i][j-1])+a[i+1][j]+a[i][j+1];
			dp[i][j][0] = min(dp[i][j-1][1],dp[i][j-1][0]+a[i-1][j])+a[i+1][j]+a[i][j+1];
		}
	}
	cout<<min(dp[n][m][0],dp[n][m][1])<<endl;
	return 0;
}

祝你 AC ~

同时也感谢你看到结尾！附赠小彩蛋：50pts 代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
	long long i,j,n,m,dp[1002][1002] = {0},a[1002][1002] = {0};
	cin>>n>>m;
	for(i = 1;i<=n;i++){
		for(j = 1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	dp[1][1] = a[1][1]+a[1][2]+a[2][1];
	for(i = 2;i<=m;i++)dp[1][i] = dp[1][i-1]+a[1][i+1]+a[2][i];
	for(i = 2;i<=n;i++)dp[i][1] = dp[i-1][1]+a[i+1][1]+a[i][2];
	for(i = 2;i<=n;i++){
		for(j = 2;j<=m;j++){
			dp[i][j] = min(dp[i][j-1]+a[i-1][j],dp[i-1][j]+a[i][j-1])+a[i][j+1]+a[i+1][j];
			if(dp[i][j]==dp[i-1][j]+a[i][j-1]+a[i][j+1]+a[i+1][j] and 
			(dp[i-1][j]==dp[i-1][j-1]+a[i-2][j]+a[i-1][j+1]+a[i][j] or dp[i-1][j]+a[i-2][j]==dp[i-1][j-1]+a[i-2][j]+a[i-1][j+1]+a[i][j]))dp[i][j]-=a[i][j-1];
			/*
			This is for:
			----
			   ↓
			   ↓
			   ↓
			And This is for:
			↓
			↓
			↓
			→→→→	
			*/ 
			if(dp[i][j]==dp[i][j-1]+a[i-1][j]+a[i][j+1]+a[i+1][j] and (dp[i][j-1]==dp[i-1][j-1]+a[i][j]+a[i][j-2]+a[i+1][j-1] or dp[i][j-1]+a[i][j-2]==dp[i-1][j-1]+a[i][j]+a[i][j-2]+a[i+1][j-1]))dp[i][j]-=a[i-1][j];
		}
	}
//	cout<<endl;
//	for(i = 1;i<=n;i++){
//		for(j = 1;j<=m;j++){
//			printf("%02lld ",dp[i][j]);
//		}
//		cout<<endl;
//	}
	cout<<dp[n][m]<<endl;
	system("pause");
}

广告：

Myblog

END~