POJ 2948 Martian Mining：棋盤型動態規劃解法

問題建模

n×m 矩陣（n,m ≤ 500），每格含兩種礦產：yeyenum（西向運送）與 bloggium（北向運送）。每格只能建一種輸送帶，礦產必須直線運送至對應工廠無轉彎。求最大總產量。

動態規劃狀態定義

dp[i][j]：處理完前 i 行、第 i 行前 j 列的最大產量。採用行優先掃描，每格決定建橫向（西）或縱向（北）帶。

前綴和優化

預計算行前綴和 x[i][j]（yeyenum 向西累加）與列前綴和 y[i][j]（bloggium 向北累加）：

x[i][j] += x[i][j-1];  // 第i行前j列yeyenum總和
y[i][j] += y[i-1][j];  // 第j列前i行bloggium總和

狀態轉移方程

當前格 (i,j) 兩種選擇取最大值：

dp[i][j] = max(
    dp[i][j-1] + y[i][j],  // 建北向帶：獲得當前列前i行bloggium
    dp[i-1][j] + x[i][j]   // 建西向帶：獲得當前行前j列yeyenum
);

邊界初始化

if (i==1 && j==1) dp[i][j] = max(y[i][j], x[i][j]);
else if (i==1) dp[i][j] = max(dp[i][j-1] + y[i][j], x[i][j]);
else if (j==1) dp[i][j] = max(y[i][j], dp[i-1][j] + x[i][j]);

完整代碼

int dp[505][505], x[505][505], y[505][505];
int main() {
    while (scanf("%d%d", &n, &m), n||m) {
        for (i=1; i<=n; i++) for (j=1; j<=m; j++) 
            scanf("%d", &x[i][j]), x[i][j] += x[i][j-1];
        for (i=1; i<=n; i++) for (j=1; j<=m; j++) 
            scanf("%d", &y[i][j]), y[i][j] += y[i-1][j];
        for (i=1; i<=n; i++) for (j=1; j<=m; j++) {
            if (i==1 && j==1) dp[i][j] = max(x[i][j], y[i][j]);
            else if (i==1) dp[i][j] = max(dp[i][j-1] + y[i][j], x[i][j]);
            else if (j==1) dp[i][j] = max(y[i][j], dp[i-1][j] + x[i][j]);
            else dp[i][j] = max(dp[i][j-1] + y[i][j], dp[i-1][j] + x[i][j]);
        }
        printf("%d\n", dp[n][m]);
    }
}

複雜度分析

• 時間：O(n×m)，單次掃描
• 空間：O(n×m)，可優化為滾動數組 O(m)
• 輸入量大，建議使用 scanf