P1004 [NOIP 2000 提高组] 方格取数

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 15;
int a[MAXN][MAXN];               // 棋盘：a[x][y] 是第 x 行第 y 列的数
int f[2 * MAXN][MAXN][MAXN];     // f[k][i][j]

// 回溯出两条最优路径（供动画演示用，输出仍然只给最大总和）。
// 两人同步走时，各自所在的行号 i1 / i2 就足以确定位置：(行, k-行)。
void backtrack(int n, vector<pair<int, int>> &p1, vector<pair<int, int>> &p2) {
    int i1 = n, i2 = n;                    // 从终点 (n,n) 往回走
    for (int k = 2 * n; k >= 2; k--) {
        p1.push_back({i1, k - i1});        // 第 k 条对角线上的位置
        p2.push_back({i2, k - i2});
        if (k == 2) break;
        int gain = a[i1][k - i1];          // 这一步两人拿到的数
        if (i1 != i2) gain += a[i2][k - i2];  // 站在同一个格子时只算一次
        int need = f[k][i1][i2] - gain;    // 上一步状态的最优值
        if (f[k - 1][i1][i2] == need) {
            // 两人行号都不变：各向右走了一步
        } else if (f[k - 1][i1 - 1][i2] == need) {
            i1--;                          // 第一个人向下走了一步
        } else if (f[k - 1][i1][i2 - 1] == need) {
            i2--;                          // 第二个人向下走了一步
        } else {
            i1--; i2--;                   // 两人同时向下走
        }
    }
    reverse(p1.begin(), p1.end());
    reverse(p2.begin(), p2.end());
}

int main() {
    int n;
    cin >> n;
    int x, y, v;
    while (cin >> x >> y >> v) {
        if (x == 0) break;                 // 一行单独的 0 表示输入结束
        a[x][y] = v;
    }

    // 核心观察：把两次行走「同步」进行——每一步两人各走一格。
    // 于是两人始终位于同一条反对角线 k = 行 + 列 上，k 从 2 走到 2n。
    // f[k][i][j]：两人分别站在第 k 条对角线的第 i 行、第 j 行时，
    // 能拿到的数的最大总和（位置由「行号」唯一确定：列号 = k - 行号）。
    // 不可达的状态置成负无穷：转移时取 max，真实值一定比它大。
    // 注意不能用正的 0x3f3f3f3f，那会让「不可达」在取 max 时压过真实值。
    memset(f, 0xc0, sizeof(f));            // 0xc0c0c0c0 = -1061109568
    f[2][1][1] = a[1][1];                  // 起点 (1,1)

    for (int k = 3; k <= 2 * n; k++) {
        int lo = max(1, k - n), hi = min(n, k - 1);  // 第 k 条对角线上的合法行号
        for (int i = lo; i <= hi; i++) {
            for (int j = lo; j <= hi; j++) {
                // 上一步的站位有 4 种组合：两人各向右或向下
                int best = max(max(f[k - 1][i][j], f[k - 1][i - 1][j]),
                               max(f[k - 1][i][j - 1], f[k - 1][i - 1][j - 1]));
                int gain = a[i][k - i];              // 第一个人这一格拿到的数
                if (i != j) gain += a[j][k - j];     // 只有不同格才都加；同格只算一次
                f[k][i][j] = best + gain;
            }
        }
    }

    vector<pair<int, int>> p1, p2;
    backtrack(n, p1, p2);                   // 还原两条最优路径（讲解用）

    cout << f[2 * n][n][n] << "\n";
    return 0;
}