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;
}