P1004. 方格取数
题面描述: 设有 N×N 的方格图 (N≤9)，我们将其中的某些方格中填入正整数，而其他的方格中则放入数字 00。如下图所示（见样例）:
A
0 0 0 0 0 0 0 0
0 0 13 0 0 6 0 0
0 0 0 0 7 0 0 0
0 0 0 14 0 0 0 0
0 21 0 0 0 4 0 0
0 0 15 0 0 0 0 0
0 14 0 0 0 0 0 0
0 0 0 0 0 0 0 0
B
某人从图的左上角的 AA 点出发，可以向下行走，也可以向右走，直到到达右下角的 BB 点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字 0）。 此人从 A 点到 B 点共走两次，试找出 2 条这样的路径，使得取得的数之和为最大。 题目链接(洛谷)
1. 两次二维 dp 解决问题的想法是错误的
本以为可以两次 dp 解决, 然而这是有问题的, 如下图
如果用两次 dp 解决的话, 第一次就找到了最优解 2 + 3 + 3, 但这导致了第二次的最优解只有 2 + 1, 最后结果为 11, 然而实际结果应该是 12
所以, 要解决问题的话, 必须要两条路同时走(并行)
2. 四维 dp
f[i1][j1][i2][j2] 表示当一条路径到达 (i1, j1) , 另一条路径到达 (i2, j2) 时, 两条路径所获得的数字的最大值.
转移方程为: f[i1][j1][i2][j2] = max(f[i1][j1 - 1][i2][j2 - 1], f[i1 - 1][j1][i2][j2 - 1]), f[i1 - 1][j1][i2 - 1][j2], f[i1][j1 - 1][i2 - 1][j2]) + w[i1][j1] + (i1 == i2 && j1 == j2 ? 0 : w[i2][j2]) 表示由 "向右" 和 "向下" 组合起来的四个状态的最大值加上他们即将移动到的坐标上的数字(如果坐标相同, 则数字只取一次)
#include <iostream>
using namespace std;
const int N = 12;
int w[N][N];
int f[N][N][N][N];
int main() {
std::ios::sync_with_stdio(false);
int n, x, y, c;
cin >> n;
while (cin >> y >> x >> c, x || y || c)
w[y][x] = c;
for (int i1 = 1; i1 <= n; i1 ++) {
for (int j1 = 1; j1 <= n; j1 ++) {
for (int i2 = 1; i2 <= n; i2 ++) {
for (int j2 = 1; j2 <= n; j2 ++) {
int sum = w[i1][j1] + ((i1 == i2 && j1 == j2) ? 0 : w[i2][j2]);
int & newState = f[i1][j1][i2][j2];
newState = max(newState, f[i1][j1 - 1][i2][j2 - 1] + sum); // right right
newState = max(newState, f[i1 - 1][j1][i2][j2 - 1] + sum); // down right
newState = max(newState, f[i1 - 1][j1][i2 - 1][j2] + sum); // down down
newState = max(newState, f[i1][j1 - 1][i2 - 1][j2] + sum); // right down
}
}
}
}
cout << f[n][n][n][n];
return 0;
}
3. 三维 dp
用变量 k 表示走过路径的长度, 则 k - i1 = j1 , k - i2 = j2.
f[k][i1][i2] 表示当走的路程为 k , 一条路线的纵坐标为 i1 , 另一条路线的纵坐标为 i2 时, 取得的数字的最大值
#include <iostream>
using namespace std;
const int N = 12;
const int M = N << 1;
int w[N][N];
int f[M][N][N];
int main() {
std::ios::sync_with_stdio(false);
int n, x, y, c, m;
cin >> n;
m = n << 1;
while (cin >> y >> x >> c, x || y || c)
w[y][x] = c;
// k = i + j
for (int k = 2; k <= m; k ++) {
for (int i1 = 1; i1 <= n; i1 ++) {
for (int i2 = 1; i2 <= n; i2 ++) {
int j1 = k - i1, j2 = k - i2;
if (j1 >= 1 && j1 <= n && j2 >= 1 && j2 <= n) {
int sum = w[i1][j1] + (i1 == i2 ? 0 : w[i2][j2]);
int & newState = f[k][i1][i2];
newState = max(newState, f[k - 1][i1 - 1][i2 - 1] + sum); // d d
newState = max(newState, f[k - 1][i1 - 1][i2] + sum); // d r
newState = max(newState, f[k - 1][i1][i2 - 1] + sum); // r d
newState = max(newState, f[k - 1][i1][i2] + sum); // r r
}
}
}
}
cout << f[m][n][n];
return 0;
}
空间优化
#include <iostream>
using namespace std;
const int N = 12;
int w[N][N];
int f[2][N][N];
int main() {
std::ios::sync_with_stdio(false);
int n, x, y, c, m;
cin >> n;
m = n << 1;
while (cin >> y >> x >> c, x || y || c)
w[y][x] = c;
// k = i + j
for (int k = 2; k <= m; k ++) {
for (int i1 = 1; i1 <= n; i1 ++) {
for (int i2 = 1; i2 <= n; i2 ++) {
int j1 = k - i1, j2 = k - i2;
int cur = k % 2, pre = (k - 1) % 2;
if (j1 >= 1 && j1 <= n && j2 >= 1 && j2 <= n) {
int sumWeight = w[i1][j1] + (i1 == i2 ? 0 : w[i2][j2]);
int & newState = f[cur][i1][i2];
newState = max(newState, f[pre][i1 - 1][i2 - 1] + sumWeight);
newState = max(newState, f[pre][i1 - 1][i2] + sumWeight);
newState = max(newState, f[pre][i1][i2 - 1] + sumWeight);
newState = max(newState, f[pre][i1][i2] + sumWeight);
} else f[cur][i1][i2] = 0;
}
}
}
cout << f[m % 2][n][n];
return 0;
}