P2295 题解
SunsetVoice
·
·
题解
更好的阅读体验~
原题传送门~
本题解概要：
- 为什么需要多加一维存储方向
- 三维 dp 思路（包括 dp 五步）
- 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 数组。~~不用说了吧~~
#### 求解目标
根据状态表示可以得出，$\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：
```cpp
#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 ~](https://www.luogu.com.cn/record/106644610)
同时也感谢你看到结尾！附赠小彩蛋：50pts 代码：
```cpp
#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](https://www.luogu.com.cn/blog/myj-cai/)
END~