漫遊曼哈頓 題解｜APCS 2026 年 11 月高級 第 2 題

前置知識

這題是方格上的動態規劃，下面的講解直接把這些當成已知，沒讀過的先讀；同一個主題兩邊都有的，對照著讀會更快上手：

• 最大連續和：NTUCPC Guide〈枚舉〉的「聰明的枚舉」一節用前綴和、邊掃邊記最小值；吳邦一《AP325》第 4 章的 P-4-13（教材 PDF 第 144～145 頁；Python 版第 4 章（II）；站上題目 ap325p413）則是「前面那段的總和是正的就接上去，不然丟掉、從這裡重新開始」。兩種都是 \(O(n)\)，本題用的是後者，而且和 P-4-13 一樣，空的一段算 \(0\)。
• 方格上的 DP，一張表不夠就開兩張：NTUCPC Guide〈多個維度的 DP〉——一張表分不出「最後是怎麼走過來的」、沒辦法避開不合法的接法時，就多開幾張表分開記；《AP325》第 6 章的 P-6-6「方格棋盤路線」（教材 PDF 第 186～187 頁；Python 版第 6 章（I）；站上題目 ap325p606）是方格上最基本的 DP：每一格的答案看「最後一步從哪裡來」。本題每一列要分「往東走過來」和「往西走過來」兩張表。

簡潔題意

\(m \times n\) 個路口排成棋盤（第 \(i\) 列、第 \(j\) 欄的路口記為 \((i, j)\)），相鄰路口之間各有一段道路，每段道路有一個好玩度（\(-100\) 到 \(100\) 的整數）。東西向的道路往東、往西都能走，南北向的道路只能由北往南走。任選一個路口出發、沿著道路走、在任選的路口結束，同一段道路最多走一次，求經過的道路好玩度總和的最大值；起點和終點可以是同一個路口（一段路都不走、總和 \(0\)），所以答案至少是 \(0\)（\(2 \le m, n \le 1000\)）。

依正確通過的測試資料筆數給分，其中：

• 子題組 1（\(40\) 分）：\(m = 2\)。
• 子題組 2（\(60\) 分）：無額外限制。

走法長什麼樣：每一列只走一段，方向固定

南北向的路只能往南走，所以一旦離開第 \(i\) 列就再也回不來：走法在每一列裡待的是連續的一段時間——從北邊某一欄走下來（或就在這一列出發），在這一列往東或往西走幾步，再從某一欄往南（或就在這一列結束）。

這段時間裡也不能回頭：往東走過一段路之後如果改往西，第一步就是剛剛那段路，同一段路走了第二次（圖 1 左）；先往西再往東也一樣。所以每一列走的是連續的一段、方向固定：從進來的那一欄一路走到離開的那一欄；兩欄相同就是在這一列一步都沒走——直直往南穿過，或剛下來就結束。

反過來，只要每一列各走一段、每一列往南的那一欄就是下一列進來的那一欄（圖 1 右），就一定是合法的走法：往南的路每條最多走一次，每一列的那一段也不會重複，連路口都不會重複。所以整條走法就是「起點那一列的一段 → 往南 → 下一列的一段 → 往南 → …… → 終點那一列的一段」，下面只要在這種走法裡找總和最大的。

先拿下 40 分：兩列時枚舉往南的那一欄

兩列時走法只有三種：只在第 1 列走、只在第 2 列走，或在某一欄 \(j\) 往南一次。往南的那一欄一固定，上下兩段就互不相干，各挑最好的：

• top[j]：第 1 列裡「一端在第 \(j\) 欄」的一段路，總和最大是多少；
• bottom[j]：第 2 列裡「一端在第 \(j\) 欄」的一段路，總和最大是多少——從第 \(j\) 欄出發往東或往西走，和走到第 \(j\) 欄的總和算法一樣。

兩者都可以一段都不走（\(0\)）。「一端在第 \(j\) 欄的最大總和」就是前置知識裡的最大連續和：另一端在西邊的，由西往東掃——前面那段是正的就接上去，不然丟掉、從 \(0\) 開始；另一端在東邊的，由東往西再掃一次；兩者取大。答案是所有 top[j]、bottom[j]、top[j] + down[j] + bottom[j] 的最大值（down[j] 是第 \(j\) 欄往南的那條路）。範例 1 在第 1 欄往南最好：第 1 列從第 3 欄往西走到第 1 欄（\(2 + 7 = 9\)），往南 \(5\)，第 2 列從第 1 欄往東走到底（\(6 + 2 - 1 + 2 = 9\)），合起來 \(23\)。

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

// road[j] 是這一列第 j 欄和第 j + 1 欄之間的路（欄從 0 起算）。
// 回傳 best[j]：這一列裡「一端在第 j 欄」的一段路，總和最大是多少（一段都不走就是 0）。
vector<int> bestEndAt(const vector<int> &road, int n) {
    vector<int> fromWest(n), fromEast(n), best(n);
    fromWest[0] = 0;
    for (int j = 1; j < n; j++)                  // 另一端在西邊：往東走到 j
        fromWest[j] = max(0, fromWest[j - 1] + road[j - 1]);
    fromEast[n - 1] = 0;
    for (int j = n - 2; j >= 0; j--)             // 另一端在東邊：往西走到 j
        fromEast[j] = max(0, fromEast[j + 1] + road[j]);
    for (int j = 0; j < n; j++) best[j] = max(fromWest[j], fromEast[j]);
    return best;
}

int main() {
    int m, n;
    cin >> m >> n;                               // 子題組 1 保證 m = 2
    vector<int> row1(n - 1), row2(n - 1), down(n);
    for (int &x : row1) cin >> x;                // 第 1 列的東西向道路
    for (int &x : row2) cin >> x;                // 第 2 列的東西向道路
    for (int &x : down) cin >> x;                // 第 1 列往南到第 2 列的道路
    vector<int> top = bestEndAt(row1, n), bottom = bestEndAt(row2, n);

    int ans = 0;                                 // 一段路都不走
    for (int j = 0; j < n; j++) {
        ans = max(ans, top[j]);                  // 只在第 1 列走
        ans = max(ans, bottom[j]);               // 只在第 2 列走
        ans = max(ans, top[j] + down[j] + bottom[j]);   // 在第 j 欄往南
    }
    cout << ans << '\n';
    return 0;
}

只要 \(O(n)\)。範例 2 有 \(5\) 列，這份程式交上去範例 2 會 WA——這是正常的，逐筆給分之下子題組 1 的 \(40\) 分穩穩到手。

從 40 分到 100 分：一列一列往下推，左右各掃一次

\(m\) 列時往南不只一次，不能再一處一處枚舉。改成一列一列往下推，只記住一件事：

• best[j]：走法目前在這一列、這一列的那一段已經走完、停在第 \(j\) 欄（接下來往南，或就在這裡結束）時，總和最大是多少。

從上一列推到下一列分兩步：

1. 進入這一列：arrive[j] = max(0, best[j] + v[i - 1][j])。從北邊下來的總和是上一列的 best[j] 加上第 \(j\) 欄往南的那條路 v[i - 1][j]；也可以乾脆就在這裡出發，總和 \(0\)——兩者取大，就是最大連續和的「前面是負的就丟掉、重新開始」。第 1 列沒有北邊，arrive 全是 \(0\)。
2. 在這一列走一段：新的 best[j] 是所有「進來的那一欄 \(a\)」當中，arrive[a] 加上從第 \(a\) 欄走到第 \(j\) 欄那段路的最大值。

第 2 步每個 \(j\) 都把所有 \(a\) 試一遍當然算得出來，但一列就要 \(n^2\) 次、整題 \(O(mn^2)\)，\(m = n = 1000\) 時約 \(10^9\) 次——本站實測約 \(0.7\)～\(1.4\) 秒（看寫法），還在時限內，但檢定現場的環境沒人保證。其實不用重算。只看 \(a\) 在 \(j\) 西邊或 \(a = j\) 的那些，取最大記成 fromWest[j]（這一段往東走到 \(j\)）：\(a\) 在西邊的，從第 \(a\) 欄走到第 \(j\) 欄都是先走到第 \(j - 1\) 欄、再多走同一段路 road[j - 1]（第 \(j - 1\) 欄和第 \(j\) 欄之間的路），所以它們當中最好的就是 fromWest[j - 1] + road[j - 1]；再和 \(a = j\)（就從第 \(j\) 欄進來）的 arrive[j] 比：

fromWest[j] = max(arrive[j], fromWest[j - 1] + road[j - 1])

由西往東掃一遍就好；\(a\) 在東邊的，同樣由東往西掃出 fromEast；best[j] 就是兩者取大。這正是子題組 1 的 bestEndAt，只是「從這裡重新開始」的 \(0\) 換成了 arrive[j]——第 1 列的 arrive 全是 \(0\)，算出來的 best 就是子題組 1 的 top。

fromWest 只從 fromWest 接、fromEast 只從 fromEast 接，兩個方向不會混在一起；混在一起，就等於在一列裡走過去又折回來。圖 2 是範例 1 整個算一遍：

答案是所有列、所有欄的 best 的最大值——終點任選。best 一定不小於 arrive、arrive 又不小於 \(0\)，所以一段路都不走的 \(0\) 自動算在裡面。

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

// road[j] 是這一列第 j 欄和第 j + 1 欄之間的路（欄從 0 起算）。
// arrive[j]：剛來到這一列第 j 欄時（從北邊下來，或就在這裡出發），已經走過的路的最大總和。
// 回傳 best[j]：在這一列走完一段、停在第 j 欄時的最大總和。
vector<int> walkRow(const vector<int> &road, const vector<int> &arrive, int n) {
    vector<int> fromWest(n), fromEast(n), best(n);
    fromWest[0] = arrive[0];
    for (int j = 1; j < n; j++)                  // 這一段往東走到 j：從 j - 1 接過來，或就從 j 進這一列
        fromWest[j] = max(arrive[j], fromWest[j - 1] + road[j - 1]);
    fromEast[n - 1] = arrive[n - 1];
    for (int j = n - 2; j >= 0; j--)             // 這一段往西走到 j
        fromEast[j] = max(arrive[j], fromEast[j + 1] + road[j]);
    for (int j = 0; j < n; j++) best[j] = max(fromWest[j], fromEast[j]);
    return best;
}

int main() {
    int m, n;
    cin >> m >> n;
    vector<vector<int>> h(m, vector<int>(n - 1)), v(m - 1, vector<int>(n));
    for (auto &row : h)                          // 東西向的道路先全部給完，
        for (int &x : row) cin >> x;
    for (auto &row : v)                          // 南北向的道路才接著給，所以兩種都整份存起來
        for (int &x : row) cin >> x;

    vector<int> arrive(n, 0), best;              // 第 1 列沒有北邊：arrive 全是 0
    int ans = 0;                                 // 一段路都不走
    for (int i = 0; i < m; i++) {
        if (i > 0)
            for (int j = 0; j < n; j++)          // 從北邊下來，或就在這裡出發
                arrive[j] = max(0, best[j] + v[i - 1][j]);
        best = walkRow(h[i], arrive, n);
        for (int j = 0; j < n; j++) ans = max(ans, best[j]);   // 停在哪個路口都可以結束
    }
    cout << ans << '\n';
    return 0;
}

每一列都只花 \(O(n)\)，整題 \(O(mn)\)，\(m = n = 1000\) 本站實測不到 \(0.5\) 秒。答案最大的情形是每段路都是 \(100\)、蛇行走完全部 \(m(n - 1)\) 段東西向的路和 \(m - 1\) 段往南的路：\(m = n = 1000\) 時 \(100 \times (1000 \times 999 + 999) = 99999900\)，int 裝得下。

測過再交：兩個範例的終點都在最後一列

範例 1 從第 1 列出發、在最後一列結束；範例 2 從第 2 列出發，三列的方向是西、東、東，最後一步往南走進最後一列就結束。沒蓋到的：每段路都是負的（一段都不走）、終點不在最後一列、直直往南穿過中間的一列、答案的最大值。

四筆都親眼看過正確，這題就穩了。