【学习笔记】四维dp
NCC79601
2019-09-04 23:11:21
# 四维dp
四维dp可以用来解决在行走方向固定的情况下，在一个矩阵内从$(1,1)$到$(n,m)$的两条不同路径的某些信息。
---
**例题** [P1004](https://www.luogu.org/problemnew/show/P1004)
# 分析
题面意思是给出一个$n\times n$的矩阵，从$(1,1)$开始取数，每次只能向右走或者向下走，数被取走后就没有了，求两次取数能够得到的最大和。
这就是 **四维dp**。
用$f[i][j][k][l]$表示第一次走到$(i,j)$，第二次走到$(k,l)$时能获得的最大和，那么由于只能向右走和向下走，所以每种状态仅有四种可能的前驱。所以转移方程就可以写成：
$$f[i][j][k][l]=max\{f_{pre}\}+a[i][j]+a[k][l]$$
特别地，如果$i=k$且$j=l$，则$f[i][j][k][l]$需要减去$a[i][j]$（每个数被取以后就变成$0$了）。
最终，在$f[n][n][n][n]$处获得答案。
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 10;
int n;
ll a[MAXN][MAXN], f[MAXN][MAXN][MAXN][MAXN];
int main() {
scanf("%d", &n);
for(int x = 1, y; x; ) {
scanf("%d %d", &x, &y);
scanf("%lli", &a[x][y]);
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
for(int k = 1; k <= n; k++)
for(int l = 1; l <= n; l++) {
f[i][j][k][l] = max(
max(f[i - 1][j][k - 1][l], f[i - 1][j][k][l - 1]),
max(f[i][j - 1][k - 1][l], f[i][j - 1][k][l - 1])
) + a[i][j] + a[k][l];
if(i == k && j == l)
f[i][j][k][l] -= a[i][j];
}
printf("%lld", f[n][n][n][n]);
return 0;
}
```
**例题** [P1006](https://www.luogu.org/problemnew/show/P1006
)
# 分析
题面意思是给出一个$n\times m$的矩阵，需要找出从$(1,1)$到$(n,m)$的两条不重合路径。
和 P1004 非常相似，也可以用四维 dp 来解决这道题（好像实际上可以优化到三维，不过我还是算了）。这道题和 P1004 的不同之处在于，P1004 是每个格子可以走多次，而这道题每个格子只能走一次。
其实这两种情况并没有什么区别，同样用$f[i][j][k][l]$表示走到$(i,j)$和$(k,l)$能得到的最大好感度。因为对于$i=k$且$j=l$的情况，将$f[i][j][k][l]$减去$a[i][j]$即表示第二次经过$(i,j)$没有意义，也就是获得的好感度为$0$。可以发现第二条路经任何不同于$(i,j)$的方格都能比经过$(i,j)$更优，那么这种状态在转移过程中自然就被舍弃掉了。所以，这里使用和 P1004 相同解法的正确性是显然的，可以直接无脑进行四维dp。
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 60;
int n, m;
ll a[MAXN][MAXN], f[MAXN][MAXN][MAXN][MAXN];
int main() {
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
scanf("%lli", &a[i][j]);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
for(int k = 1; k <= n; k++)
for(int l = 1; l <= m; l++) {
f[i][j][k][l] = max(
max(f[i - 1][j][k - 1][l], f[i - 1][j][k][l - 1]),
max(f[i][j - 1][k - 1][l], f[i][j - 1][k][l - 1])
) + a[i][j] + a[k][l];
if(i == k && j == l)
f[i][j][k][l] -= a[i][j];
}
printf("%lli", f[n][m][n][m]);
return 0;
}
```