投資遊戲 題解｜APCS 2023 年 10 月高級 第 4 題

前置知識

這題是最大連續和多加一個維度，下面的講解直接把這些當成已知，沒讀過的先讀；同一個主題兩邊都有的，對照著讀會更快上手：

• 最大連續子陣列和：吳邦一《AP325》第 4 章的 P-4-13（教材 PDF 第 144～145 頁；站上 ap325p413）——「以第 \(i\) 天收尾的最佳區間」只有「接在前一天後面」或「從今天重新開始」兩種可能。
• DP 的狀態與轉移、多加一個維度：NTUCPC Guide〈狀態與轉移〉與〈多個維度的 DP〉——一個 dp 式描述不完的情況（這題：用了幾張金牌）就多開一維。
• 前綴和：NTUCPC Guide〈前綴和與差分〉——子題組 1 枚舉區間時用。

簡潔題意

\(n\) 天的收益 \(a_1, \ldots, a_n\)（可能是負的）。選一段連續的日子投資，這段裡至多 \(k\) 天可以用金牌把那天的收益當成 \(0\)，其他日子照算；也可以完全不投資、收益 \(0\)。求最高總收益（\(1 \le n \le 150000\)，\(0 \le k \le 20\)，\(-10000 \le a_i \le 10000\)）。

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

• 子題組 1（\(20\) 分）：\(k = 0\)，\(n \le 2000\)。
• 子題組 2（\(20\) 分）：\(k = 0\)。
• 子題組 3（\(60\) 分）：\(1 \le k \le 20\)。

先拿下 20 分：枚舉投資的頭尾

\(k = 0\) 就是「最大連續和」。\(n \le 2000\) 時直接枚舉投資的第一天 \(l\) 與最後一天 \(r\)，用前綴和 \(O(1)\) 算出這段的總和取最大；best 從 \(0\) 起算，就包含了「完全不投資」。

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

int main() {
    int n, k;
    cin >> n >> k;                               // 這個子題組 k = 0
    vector<int> prefix(n + 1, 0);                // prefix[i] = a[1] + ... + a[i]
    for (int i = 1; i <= n; i++) {
        int gain;
        cin >> gain;
        prefix[i] = prefix[i - 1] + gain;
    }
    int best = 0;                                // 完全不投資＝ 0
    for (int l = 1; l <= n; l++)
        for (int r = l; r <= n; r++)             // 投資第 l 天到第 r 天
            best = max(best, prefix[r] - prefix[l - 1]);
    cout << best << '\n';
    return 0;
}

\(O(n^2)\)，\(n = 2000\) 只有 \(2 \times 10^6\) 次；\(n = 150000\) 本站實測 \(6.8\) 秒，子題組 2 會超時。範例 2、3 有金牌，這份程式印 6 是正常的——子題組 1 的 \(20\) 分穩穩到手。

從 20 分到 40 分：以今天收尾的最佳收益

令 endHere ＝「投資到今天為止」的最佳收益，一天都不投資的空段算 \(0\)。今天的收益接在昨天的 endHere 後面，接完如果變成負的，那不如什麼都不投資（\(0\)）——所以 endHere = max(0, endHere + gain)。endHere 永遠不是負的，正資產就繼承下去、負的就放掉重新開始；全部日子的 endHere 取最大就是答案。

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

int main() {
    int n, k;
    cin >> n >> k;                               // 這個子題組 k = 0
    int best = 0, endHere = 0;                   // endHere：以今天收尾的最佳收益（空的＝ 0）
    for (int i = 0; i < n; i++) {
        int gain;
        cin >> gain;
        endHere = max(0, endHere + gain);        // 接在昨天後面，或者今天才開始（空段 0 加上今天）
        best = max(best, endHere);
    }
    cout << best << '\n';
    return 0;
}

\(O(n)\)，連陣列都不用開。子題組 1、2 的 \(40\) 分穩穩到手。

從 40 分到 100 分：多記「用了幾張金牌」

有金牌之後，「投資到今天為止」還不夠描述狀態——同樣投資到今天，用掉幾張金牌會影響之後還能不能跳過虧損的日子。所以多開一維：

endHere[j] ＝ 投資到今天為止、至多用了 \(j\) 張金牌的最佳收益（空段算 \(0\)）。

今天有三種可能，三者取大：

• 今天照常計入：endHere[j] + gain。
• 一天都不投資：\(0\)。
• 今天用一張金牌（今天還在區間裡，只是收益不算）：昨天的 endHere[j - 1]，一毛不加。

圖 1 是範例 2（\(k = 2\)）整張表，標色的格子是答案 \(12\) 的來源：九天全投資，第 3 天與第 7 天用金牌跳過 \(-2\) 與 \(-5\)。

每一格只看「左邊一格」與「左上一格」，所以用一維陣列滾動、\(j\) 由大到小更新：算 endHere[j] 時 endHere[j - 1] 還是昨天的值。由小到大更新的話 endHere[j - 1] 已經變成今天的值，「用金牌跳過今天」這條路就不見了——範例 2、3 會印出跟沒有金牌一樣的 6。

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

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> endHere(k + 1, 0);               // endHere[j]：以今天收尾、至多用 j 張金牌的最佳收益
    int best = 0;
    for (int i = 0; i < n; i++) {
        int gain;
        cin >> gain;
        for (int j = k; j >= 0; j--) {           // 由大到小：算 endHere[j] 時 endHere[j-1] 還是昨天的值
            int value = max(0, endHere[j] + gain);           // 今天照常計入（或從今天重新開始）
            if (j > 0) value = max(value, endHere[j - 1]);   // 今天用一張金牌：收益不變、多用一張
            endHere[j] = value;
            best = max(best, value);
        }
    }
    cout << best << '\n';
    return 0;
}

\(O(nk)\)，\(n = 150000\)、\(k = 20\) 只有 \(3 \times 10^6\) 次。答案最大是 \(150000 \times 10000 = 1.5 \times 10^9\)，int 的上限 \(2147483647\) 裝得下；不想算就用 long long，兩種都對。金牌是「至多」用：全是正收益時一張都不用最好，程式裡 endHere[j] 永遠不比 endHere[j - 1] 小，自然做到這點。

測過再交：範例沒有「金牌用不完」的局面

四個範例蓋到了 \(k = 0\)（範例 1、4）、全部虧損印 \(0\)（範例 4）、金牌有用武之地（範例 2、3）。沒蓋到：只有一天、全是正收益（金牌該一張都不用）、金牌不夠把虧損跳完、「先找最賺的一段再刪負數」會錯的局面、答案頂到上限。

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