概览
同方格取数,只要分析到关于两条路线重合的部分都只是记录一次即可
题解
代码
1. 修改版
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 55;
int n, m;
int w[N][N];
int f[N * 2][N][N];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
scanf("%d", &w[i][j]);
for (int k = 2; k <= n + m; k ++) {
for (int i1 = max(1, k - m); i1 <= min(k - 1, n); i1 ++) {
for (int i2 = max(1, k - m); i2 <= min(k - 1, n); i2 ++) {
int j1 = k - i1, j2 = k - i2;
if (j1 >= 1 && j1 <= m && j2 >= 1 && j2 <= m) {
int t = w[i1][j1];
if (i1 != i2) t += w[i2][j2];
int &x = f[k][i1][i2];
x = max(x, f[k - 1][i1 - 1][i2 - 1] + t);
x = max(x, f[k - 1][i1 - 1][i2] + t);
x = max(x, f[k - 1][i1][i2 - 1] + t);
x = max(x, f[k - 1][i1][i2] + t);
}
}
}
}
printf("%d\n", f[m + n][n][n]);
return 0;
}
2. 精炼版
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 55;
int n, m; // n: rows, m: cols
int w[N][N];
int f[N * 2][N][N];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
scanf("%d", &w[i][j]);
// 实际的坐标条件x \in [1,n], y \in [1, n] x=i1, y=k-i1
for (int k = 2; k <= n + m; k ++)
for (int x1 = max(1, k - m); x1 <= min(k - 1, n); x1 ++)
for (int x2 = max(1, k - m); x2 <= min(k - 1, n); x2 ++)
{
int t = w[x1][k - x1];
if (x2 != x1) t += w[x2][k - x2];
for (int a = 0; a <= 1; a ++)
for (int b = 0; b <= 1; b ++)
f[k][x1][x2] = max(f[k][x1][x2], f[k - 1][x1 - a][x2 - b] + t); }
printf("%d\n", f[n + m][n][n]); // take care!
return 0;
}