POJ 2948 Martian Mining 詳解

題目：n×m (≤500) 礦區，每格有 yeyenum（西向運）與 bloggium（北向運）兩種礦產。每格只能建一種輸送帶（西向或北向）。礦產必須沿直線無轉彎運達對應工廠（西/北邊界）。若路徑上遇到不同方向輸送帶，礦產損失。求最大化總運達量。

核心洞察：DP 狀態壓縮「切割線」

考慮從西北角 (1,1) 到東南角 (n,m) 的路徑。每一步向右或向下。這條路徑將礦區分為兩部分：
- 路徑上方/左側區域：適合建北向帶（運 bloggium 北上）。
- 路徑下方/右側區域：適合建西向帶（運 yeyenum 西進）。
路徑本身的格子可任選，但最優解中路徑即為「分界線」。

DP 定義

dp[i][j]：處理完前 i 行、前 j 列（即子矩陣 [1..i][1..j]）的最大運達量。
轉移：最後一步來自 (i-1,j)（向下）或 (i,j-1)（向右）。

• 從 (i-1,j) 向下：第 i 行 [1..j] 區間建西向帶 → 獲得 rowSum[i][j]（第 i 行前 j 列 yeyenum 和）。
• 從 (i,j-1) 向右：第 j 列 [1..i] 區間建北向帶 → 獲得 colSum[i][j]（第 j 列前 i 行 bloggium 和）。

轉移方程：

dp[i][j] = max( dp[i-1][j] + rowSum[i][j],  dp[i][j-1] + colSum[i][j] )

預處理前綴和

• rowSum[i][j] = 第 i 行第 1~j 列 yeyenum 之和。
• colSum[i][j] = 第 j 列第 1~i 行 bloggium 之和。

輸入時直接累加計算，O(nm)。

參考代碼 (C++)

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

const int MAX = 505;
long long rowSum[MAX][MAX], colSum[MAX][MAX];
long long dp[MAX][MAX];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    while (cin >> n >> m) {
        if (n == 0 && m == 0) break;
        // 讀 yeyenum 並計算行前綴和
        for (int i = 1; i <= n; ++i) {
            rowSum[i][0] = 0;
            for (int j = 1; j <= m; ++j) {
                long long x; cin >> x;
                rowSum[i][j] = rowSum[i][j-1] + x;
            }
        }
        // 讀 bloggium 並計算列前綴和
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                long long x; cin >> x;
                colSum[i][j] = colSum[i-1][j] + x;
            }
        }
        // DP
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                dp[i][j] = max(dp[i-1][j] + rowSum[i][j],
                               dp[i][j-1] + colSum[i][j]);
            }
        }
        cout << dp[n][m] << '\n';
    }
    return 0;
}

關鍵點總結

1. 幾何直覺 → DP 切割線：最優輸送帶佈局等價於一條從西北到東南的單調路徑分界。
2. 前綴和 O(1) 區間查詢：行/列累加和預處理，轉移 O(1)。
3. DP 狀態無後效性：dp[i][j] 只依賴左/上狀態，標準二維網格 DP。
4. 長整型：500×500×1000 = 2.5e8，需 long long。

複雜度分析

面試延伸

• 輸出方案：回溯 dp 重構分界線，再決定每格輸送帶方向。
• 三維擴展：若有三種礦產/方向，狀態需擴展為三維切割面，複雜度指數上升。
• 帶權轉向代價：若允許轉彎但有代價，狀態需增加「進入方向」維度。

總結

POJ 2948 是「二維 DP 分界線」的經典範例。它將看似複雜的雙向流約束，通過幾何觀察轉化為單調路徑分割問題，最終歸結為簡單的 dp[i][j] = max(dp[i-1][j]+row, dp[i][j-1]+col)。此類「網格分割、單調邊界」模式廣泛見於圖像分割、倉儲規劃、晶片佈線等領域。