洛谷 P1004 [NOIP2000 提高组] 方格取数

题意：n*n的方格，从左上角到右下角两次。每一次经过的路径中，如果有数字，数字都会变成0并计数。求两次路径的最大计数。

思路：线性dp，从左上角到右下角步数固定为 2 * n - 2步。 初始时0步dp[0][1][1] = grid[1][1]，知道了x1和x2可以确定对应的y，可以直接进行状态转移。 可以增加剪枝：x <= min(n, s1 + 1)。

总结：
1 忽略了当到了终点时x1 == x2的情况，被直接跳过了。
2 忽略了x不动，当前步数都是由y移动的情况（4种转移状态之一）

  void solve(){int n;cin >> n;vector<vector<int>> grid(n + 1, vector<int>(n + 1, 0));{int x, y, k;while (cin >> x >> y >> k && (x && y && k)){grid[x][y] = k;}}vector<vector<vector<int>>> dp(2, vector<vector<int>>(n + 1, vector<int>(n + 1)));dp[0][1][1] = grid[1][1];int p = 0;for (int s = 1; s <= 2 * n - 2; ++s){p ^= 1;for (int x1 = 1; x1 <= min(n, s + 1); ++x1){for (int x2 = 1; x2 <= min(n, s + 1); ++x2){if ((x1 != x2) || s == 2 * n - 2){int y1 = s + 2 - x1;int y2 = s + 2 - x2;if (y1 <= n && y2 <= n){auto& cur = dp[p][x1][x2];if (x1 > 1 && x2 > 1){cur = max(cur, dp[p ^ 1][x1 - 1][x2 - 1] + grid[x1][y1] + grid[x2][y2]);}if (x1 > 1 && y2 > 1){cur = max(cur, dp[p ^ 1][x1 - 1][x2] + grid[x1][y1] + grid[x2][y2]);}if (x2 > 1 && y1 > 1){cur = max(cur, dp[p ^ 1][x1][x2 - 1] + grid[x1][y1] + grid[x2][y2]);}if (y1 > 1 && y2 > 1){cur = max(cur, dp[p ^ 1][x1][x2] + grid[x1][y1] + grid[x2][y2]);}}}}}}/*for (int i = 1; i <= n; ++i){for (int j = 1; j <= n; ++j){cout <<  grid[i][j] << " \n"[j == n];}}for (int i = 1; i <= n; ++i){for (int j = 1; j <= n; ++j){cout <<  dp[p][i][j] << " \n"[j == n];}}*/cout << dp[p][n][n] - grid[n][n] << '\n';}