勇者修煉 題解｜APCS 2020 年 10 月高級 第 3 題

前置知識

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

• 最大連續子陣列（Kadane）：吳邦一《AP325》第 4 章的 P-4-13（教材 PDF 第 144～145 頁；站上題目 ap325p413）——「以第 \(i\) 格結尾的最大總和，不是接上前一段就是從自己重新開始」。本題子題組 1 就是它，但不能選空的。
• 方格上的 DP：AP325 第 6 章的 P-6-6「方格棋盤路線」（PDF 第 186～187 頁；站上題目 ap325p606）——只能往右、往下時，每一格的答案由左邊與上面的格子決定；NTUCPC Guide〈多個維度的 DP〉講「一個 dp 式不夠就開兩個」——本題每一列要分「從左邊走過來」與「從右邊走過來」兩張表。
• 前綴和：NTUCPC Guide〈前綴和與差分〉——子題組 2 要用它算一列裡任一段的總和。

簡潔題意

\(m\) 列 \(n\) 行的整數方格，從最上面一列任一格出發，每步往左、右或下走一格，不能重複經過格子，走到最下面一列任一格結束，求經過格子（含起點、終點）的數字總和最大是多少（\(1 \le m \le 50\)，\(1 \le n \le 10^4\)，每格介於 \(-100\) 與 \(100\)）。

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

• 子題組 1（\(20\) 分）：\(m = 1\)，\(n \le 100\)。
• 子題組 2（\(30\) 分）：\(n \le 100\)。
• 子題組 3（\(50\) 分）：無額外限制。

先拿下 20 分：只有一列就是最大連續子陣列

只有一列時，路線就是這一列裡連續的一段（往左或往右走，不能回頭，不然會重複經過），而且起點本身一定要算，不能什麼都不選。令 endHere ＝ 以目前這格結尾的最大總和：前面那段總和是正的就接上去，否則從這格重新開始；所有 endHere 的最大值就是答案。

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

int main() {
    int m, n;
    cin >> m >> n;                                   // 子題組 1：m = 1
    int best = -1000000000, endHere = 0;             // endHere：以目前這格結尾的最大總和
    for (int j = 0; j < n; j++) {
        int x;
        cin >> x;
        if (endHere > 0) endHere += x;               // 前面那段是正的就接下去
        else endHere = x;                            // 不然從這格重新開始（至少要走這一格）
        best = max(best, endHere);
    }
    cout << best << '\n';
    return 0;
}

範例就是一列：\(2 + 1 + 4 = 7\)。全是負數時答案是最大的那一格（負的），best 的初始值要夠小，不能用 \(0\)。這份程式只讀第一列，\(m > 1\) 的測資會錯，子題組 1 的 \(20\) 分穩穩到手。

路線長什麼樣：每一列只走一段，兩端分別是「進來」與「離開」的格子

不能往上走，所以路線由上往下一列一列經過；在同一列裡不能先往左再往右（會重複經過格子），所以每一列走的是連續的一段，而且只朝一個方向：從上面一列在第 \(enter\) 行走進來，橫著走到第 \(leave\) 行，再往下走到下一列的第 \(leave\) 行；第一列的 \(enter\) 是起點，最後一列的 \(leave\) 是終點。圖 1 的路線在第 1 列往右走、第 2 列不橫走、第 3 列往左走。

所以只要記住「走完某一列、停在第 \(j\) 行準備往下」的最大得分 \(best[j]\)，下一列的每個 \(leave\) 就能從上一列的每個 \(enter\) 接過來。

從 20 分到 50 分：枚舉進來與離開的行，用前綴和算那一段

對每一列，算這一列的前綴和 prefix（prefix[k] ＝ 前 \(k\) 格的和），那一段 \([\min(enter, leave), \max(enter, leave)]\) 的總和就是兩個前綴和相減。新的 \(cur[leave]\) ＝ 所有 \(enter\) 當中 prev[enter] + 那一段的和 的最大值。第一列之前沒有任何得分，prev 全設 \(0\) 代表起點任選；之後每一列的 prev 都是真的走過來的分數，負的也要照實留著。

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

int main() {
    int m, n;
    cin >> m >> n;
    vector<int> prev(n, 0);                          // prev[j]：上一列在第 j 行往下走時的最大得分；第一列之前全是 0
    for (int i = 0; i < m; i++) {
        vector<int> a(n), prefix(n + 1, 0);
        for (int j = 0; j < n; j++) {
            cin >> a[j];
            prefix[j + 1] = prefix[j] + a[j];        // prefix[k]：這一列前 k 格的和
        }
        vector<int> cur(n, -1000000000);             // cur[j]：這一列在第 j 行往下走（或結束）時的最大得分
        for (int enter = 0; enter < n; enter++)      // 從上一列的第 enter 行進來
            for (int leave = 0; leave < n; leave++) {   // 橫著走到第 leave 行
                int lo = min(enter, leave), hi = max(enter, leave);
                cur[leave] = max(cur[leave], prev[enter] + prefix[hi + 1] - prefix[lo]);
            }
        prev = cur;
    }
    cout << *max_element(prev.begin(), prev.end()) << '\n';
    return 0;
}

每列 \(O(n^2)\)、共 \(O(mn^2)\)，\(n \le 100\) 時瞬間跑完；\(n = 10^4\) 時是 \(50 \times 10^8\) 次，本站實測 \(6.2\) 秒超時，子題組 1、2 的 \(50\) 分穩穩到手。

從 50 分到 100 分：左右各掃一遍，不用枚舉進來的行

\(cur[leave]\) 要看所有 \(enter\)，太慢的原因是每一格都從頭算整段。換個角度：路線走到這一列的第 \(j\) 行時，最後一步只有三種——從上面進來（prev[j]）、從左邊那格走過來、從右邊那格走過來。但「從左邊走過來」和「從右邊走過來」不能混在同一張表裡，否則會算出先往左再往右的路線（重複經過格子）。所以開兩張表：

• fromLeft[j] ＝ 走到第 \(j\) 行、而且這一列只往右走的最大得分 ＝ \(\max(\text{prev}[j], \text{fromLeft}[j - 1]) + a[j]\)，由左往右算。
• fromRight[j] ＝ 走到第 \(j\) 行、而且這一列只往左走的最大得分 ＝ \(\max(\text{prev}[j], \text{fromRight}[j + 1]) + a[j]\)，由右往左算。

這一列在第 \(j\) 行往下走的最大得分就是兩者取大。fromLeft[j] 只接受「從上面進來」或「從左邊同方向走過來」，往右走的路線到第 \(j\) 行時的每一種進法都被算到，又不可能回頭。圖 1 下半的表就是這樣一列一列算出來的，最後一列的最大值 \(16\) 是答案。

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

int main() {
    int m, n;
    cin >> m >> n;
    vector<int> prev(n, 0);                          // prev[j]：上一列在第 j 行往下走時的最大得分；第一列之前全是 0
    for (int i = 0; i < m; i++) {
        vector<int> a(n), fromLeft(n), fromRight(n);
        for (int j = 0; j < n; j++) cin >> a[j];
        for (int j = 0; j < n; j++) {                // fromLeft[j]：最後一步是「從上面進來」或「從左邊走過來」
            fromLeft[j] = prev[j];
            if (j > 0) fromLeft[j] = max(fromLeft[j], fromLeft[j - 1]);
            fromLeft[j] += a[j];
        }
        for (int j = n - 1; j >= 0; j--) {           // fromRight[j]：最後一步是「從上面進來」或「從右邊走過來」
            fromRight[j] = prev[j];
            if (j < n - 1) fromRight[j] = max(fromRight[j], fromRight[j + 1]);
            fromRight[j] += a[j];
        }
        for (int j = 0; j < n; j++) prev[j] = max(fromLeft[j], fromRight[j]);
    }
    cout << *max_element(prev.begin(), prev.end()) << '\n';
    return 0;
}

每列三趟 \(O(n)\)，總共 \(O(mn)\)，剛才 \(6.2\) 秒的測資本站實測 \(0.07\) 秒。得分最多 \(50 \times 10^4 \times 100 = 5 \times 10^7\)、最少 \(50 \times (-100) = -5000\)（\(n = 1\) 時被迫一路往下），int 都裝得下。

測過再交：範例只有一列、答案是正的

範例是 \(m = 1\)，什麼陷阱都沒有。沒蓋到：答案是負的（不能什麼都不走）、要往左走才拿得到的分數、同一列不能來回、以及起點不一定在最左邊。

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