Codeforces 214E Relay Race：三維 DP 解決雙人接力最大得分

題目重述

n × n 網格，每格有分數（可為負）。Furik 從 (1,1) 走到 (n,n)，每步只能向下或向右；Rubik 從 (n,n) 走回 (1,1)，每步只能向上或向左。兩人走過的格子分數只算一次。求最大總分。n ≤ 300，分數絕對值 ≤ 1000。

關鍵轉化

兩人同步移動：設兩人走過的總步數相同。定義 k = i1 + j1 = i2 + j2 為步數（從 2 到 2n）。狀態 dp[k][i1][i2] 表示兩人分別位於 (i1, k-i1)、(i2, k-i2) 時的最大得分。轉移從上一步的四種組合（下/右）取最大值。若兩人位於同一格，分數只加一次。

狀態轉移方程

dp[k][i1][i2] = max(
    dp[k-1][i1-1][i2-1], // 兩人都向下
    dp[k-1][i1-1][i2],   // Furik 下，Rubik 右
    dp[k-1][i1][i2-1],   // Furik 右，Rubik 下
    dp[k-1][i1][i2]      // 兩人都向右
) + val(i1, k-i1) + (i1==i2 ? 0 : val(i2, k-i2));

初始化與邊界

• dp 初始化為極小值（如 -1e9），因有負分。
• dp[2][1][1] = a[1][1]（起點重疊）。
• 索引檢查：1 ≤ i1,i2 ≤ n、1 ≤ k-i1,k-i2 ≤ n。

完整 C++ 代碼

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 305;
const int INF = -1e9;
int a[MAXN][MAXN];
int dp[2*MAXN][MAXN][MAXN];

int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                scanf("%d", &a[i][j]);

        if (n == 1) { printf("%d\n", a[1][1]); continue; }

        // 初始化
        for (int k = 0; k <= 2*n; ++k)
            for (int i = 0; i <= n; ++i)
                for (int j = 0; j <= n; ++j)
                    dp[k][i][j] = INF;

        dp[2][1][1] = a[1][1];

        for (int k = 3; k <= 2*n; ++k) {
            for (int i1 = 1; i1 <= n; ++i1) {
                int j1 = k - i1;
                if (j1 < 1 || j1 > n) continue;
                for (int i2 = 1; i2 <= n; ++i2) {
                    int j2 = k - i2;
                    if (j2 < 1 || j2 > n) continue;

                    int best = INF;
                    best = max(best, dp[k-1][i1-1][i2-1]);
                    best = max(best, dp[k-1][i1-1][i2]);
                    best = max(best, dp[k-1][i1][i2-1]);
                    best = max(best, dp[k-1][i1][i2]);
                    if (best == INF) continue;

                    int add = a[i1][j1];
                    if (i1 != i2) add += a[i2][j2];
                    dp[k][i1][i2] = best + add;
                }
            }
        }
        printf("%d\n", dp[2*n][n][n]);
    }
    return 0;
}

複雜度與優化

• 狀態數 O(n^3)，n=300 時約 2700 萬，時間 O(n^3) 可通過。
• 空間 O(n^3) 約 108 MB，可用滾動數組優化至 O(n^2)。
• 注意初始化為極小值而非 0，因分數可為負。