题意

给定一个 m×n 的矩阵 a，要求从 (1,1) 到 (m,n) 的最大路径与次大路径之和（只可往下或往右）。

思路

看到题面，马上可以想到 DP。观察数据范围，发现 1≤m,n≤50，考虑复杂度为 O(n4) 的 DP。

我们先来做一做简化版的题面：
给定一个 m×n 的矩阵 a，要求从 (1,1) 到 (m,n) 的最大路径（只可往下或往右）。
令 fx,y​ 表示从 (1,1) 到 (x,y) 的最大路径。
我们知道，对于每一个 (i,j)，它要么是从 (i−1,j)（也就是左面）过来的，要么是从 (i,j−1)（也就是上面）过来的。所以我们计算 fi,j​ 时，只需取 fi−1,j​ 与 fi,j−1​ 的最大值再加上 ai,j​ 即可。很容易推出状态转移方程：

fi,j​←max(fi−1,j​,fi,j−1​)+ai,j​

这就是简化版的做法了。

令 fx1,y1,x2,y2​ 表示：
从 (1,1) 到 (x1,y1) 的最大数之和与从 (1,1) 到 (x2,y2) 的最大数之和的和。
接下来我们仿照简化版来推状态转移方程。对于每一个 (i,j,k,t)，它是从

• (i−1,j,k−1,t)
• (i−1,j,k,t−1)
• (i,j−1,k−1,t)
• (i,j−1,k,t−1)

中的一个点过来的。我们只需取这四个点中的最大值，再加上 ai,j​ 和 ak,t​ 即可。状态转移方程：

fi,j,k,t​←max(fi−1,j,k−1,t​,fi−1,j,k,t−1​,fi,j−1,k−1,t​,fi,j−1,k,t−1​)+ai,j​+ak,t​

注意，还有一个特例：
当 (i,j)=(k,t) 时，两点所处位置相同，所以我们在计算 fi,j,k,t​ 时需要减去 ai,j​（或 ak,t​）。

代码

#include <iostream>
using namespace std;
int a[60][60];
int dp[60][60][60][60];
int main() {
	int m, n;
	cin >> m >> n;
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> a[i][j];
		}
	}
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= m; k++) {
				for (int t = 1; t <= n; t++) {
					int maxn1 = max(dp[i - 1][j][k - 1][t], dp[i - 1][j][k][t - 1]);
					int maxn2 = max(dp[i][j - 1][k - 1][t], dp[i][j - 1][k][t - 1]);
					int maxn = max(maxn1, maxn2);
					dp[i][j][k][t] = maxn + a[i][j] + a[k][t];
					if (i == k && j == t) {
						dp[i][j][k][t] -= a[i][j];
					}
				}
			}
		}
	}
	cout << dp[m][n][m][n];
	return 0;
}