P1006 传纸条 题解
然而已经
·
·
题解
感觉应该对2条路径走到一个点（重复点）处理方法不懂
举例一个四维dp的里的做法（三维等解法的大佬不要嘲笑）
首先，起点到终点走两次与题意是等效的。
四位dp很容易想，但对于大佬题解里重复点的处理，蒟蒻实在是有点不太明白
我们可以这样想，2条路径不相交，那么肯定一条在上面，一条在下面，如图是随便画的2条路径
那么对于$k$，我们只需枚举$[i+1, m]$,$l$只需枚举$[1,j-1]$即可
这样就不用判重啦
由于最后dp不到终点，但其实黑色路径走到终点上方的点，红色路径走到终点左边的点就是答案,即`f[m-1][n][m][n-1]`
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define INF = 0x3f3f3f3f
int a[51][51], f[51][51][51][51];
int m, n;
int max(int i, int j, int k, int l){
int m = max(i, j), n = max(k, l);
return max(m, n);
}
int main()
{
cin >> m >> n;
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++)
{
cin >> a[i][j];
}
}
f[1][1][1][1] = 0; //garbage
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
for(int k = i+1; k <= m; k++){
for(int l = 1; l < j; l++){
f[i][j][k][l] = max(
f[i][j-1][k][l-1],
f[i][j-1][k-1][l],
f[i-1][j][k-1][l],
f[i-1][j][k][l-1]
)+a[i][j]+a[k][l];
}
}
}
}
cout << f[m-1][n][m][n-1] << endl;
return 0;
}
```