题解：P1006 [NOIP 2008 提高组] 传纸条
Tomwsc
·
·
题解
P1006 [NOIP 2008 提高组] 传纸条 题解
Myblog
本人习惯先 n 后 m，所以下面的 n 和 m 均与题目相反。
题意
找出两条从 (1,1) 到 (n,m) 的路径，使这两条路径之和最大。
思路
考虑 dp。
设 dp_{i,j,p,q} 表示第一条路径走到 (i,j)，第二条路径走到 (p,q) 的最大值。
接下来我们推方程：
不难发现 (i,j) 可以从 (i-1,j) 和 (i,j-1) 转移而来，而 (p,q) 可以从 (p-1,q) 和 (p,q-1) 转移而来。同时，因为是两条路径同时计算，所以转移时还要加上 a_{i,j} 和 a_{p,q}。
于是得到转移方程：
dp_{i,j,p,q}=\max(dp_{i-1,j,p-1,q},dp_{i-1,j,p,q-1},dp_{i,j-1,p-1,q},dp_{i,j-1,p,q-1})+a_{i,j}+a_{p,q}
注意到为了使这两条路径不相交，我们还需要改变一下枚举方式。可以让第一条路径只在矩阵的上半部分转移，而剩下的部分便让第二条路径进行转移。于是得到 i，j，p，q 这 4 个变量的枚举方式：
最后，因为这样子 dp 不会相交，所以两条路径不会到达 $(n,m)$。但因为 $a_{n,m}=0$，所以最后答案也就可以转化为：$dp_{n-1,m,n,m-1}$。
## 代码
```cpp
#include<bits/stdc++.h>
#define int long long
#define inf 1ll << 62
using namespace std;
const int MAXN = 55;
int n , m;
int a[MAXN][MAXN];
int dp[MAXN][MAXN][MAXN][MAXN];
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for(register int i = 1;i <= n;i ++)
for(register int j = 1;j <= m;j ++)
cin >> a[i][j];
for(register int i = 1;i <= n;i ++)
for(register int j = 1;j <= m;j ++)
for(register int p = i + 1;p <= n;p ++)
for(register int q = 1;q < j;q ++)
dp[i][j][p][q] = max(dp[i - 1][j][p - 1][q] , max(dp[i - 1][j][p][q - 1] , max(dp[i][j - 1][p - 1][q] , dp[i][j - 1][p][q - 1]))) + a[i][j] + a[p][q];
cout << dp[n - 1][m][n][m - 1] << '\n';
return 0;
}
```