美食博覽會 題解｜APCS 2021 年 9 月高級 第 4 題

前置知識

這題是「DP 的轉移寫出來之後還要再砍一刀」的經典，下面的講解直接把這些當成已知，沒讀過的先讀；同一個主題兩邊都有的，對照著讀會更快上手：

• 雙指標（滑動視窗）：NTUCPC Guide〈雙指標〉——「右端往右推時，左端只會往右、不會往回」，所以兩個指標各走一趟就能找出每個右端點對應的最長合法區段。
• DP 的狀態與轉移：NTUCPC Guide〈狀態與轉移〉、〈多個維度的 DP〉——本題的狀態是「考慮到第幾攤、用了幾個人」兩個維度。

簡潔題意

\(n\) 個攤位排成一列，第 \(i\) 攤賣品項 \(a_i\)。\(k\) 位試吃員各自挑一個攤位開始，依編號往後一攤一攤吃；遇到自己已經吃過的品項就不吃、直接離開。每個攤位只算一次，求 \(k\) 個人合起來最多能造訪幾個攤位（\(1 \le n \le 10^6\)，\(1 \le k \le 20\)，\(n \times k \le 5 \times 10^6\)，品項是小於 \(10^5\) 的非負整數）。

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

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

換句話說：在這個序列上挑出至多 \(k\) 段互不重疊的連續區段，每一段裡的品項都不重複，總長度最大是多少。兩個人的路線重疊沒有好處——重疊的攤位只算一次，把後面那個人的起點往後挪，攤位數不會變少。

先拿下 50 分：一個人就是最長的不重複區段

只有一個人時，答案就是最長的、品項不重複的連續區段。固定右端點 \(j\)，往左最多能延伸到哪裡？記 \(L[j]\) ＝「以第 \(j\) 攤結尾、品項都不重複」的最長區段的左端。右端從 \(j - 1\) 推到 \(j\) 時，左端只會往右走：新加入的品項 \(a_j\) 如果在區段裡出現過（上一次出現在 \(\text{last}[a_j]\)），左端就得推到它的下一攤；否則不動。

攤位從 \(1\) 編號，last 全部初始化成 \(0\) 就代表「還沒出現過」；品項可以是 \(0\)，所以 last 的下標是品項、不是「品項減一」。

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

const int MAX_N = 1000005;
const int MAX_A = 100005;
int a[MAX_N], L[MAX_N];        // L[j]：以第 j 攤結尾的最長不重複區段，左端在哪
int last[MAX_A];               // last[v]：品項 v 上一次出現在第幾攤（0 = 還沒出現）

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];

    int left = 1, ans = 0;
    for (int j = 1; j <= n; j++) {
        left = max(left, last[a[j]] + 1);  // a[j] 上次出現在區段裡 → 左端推到它後面
        last[a[j]] = j;
        L[j] = left;
        ans = max(ans, j - L[j] + 1);
    }
    cout << ans << '\n';
    return 0;
}

left 只會往右走，整個迴圈 \(O(n)\)。範例 1 的 \(L\) 是 \(1, 1, 2, 2, 4\)，最長的是以第 \(4\) 攤結尾的 \(2 \sim 4\)，答案 \(3\)。\(k > 1\) 時這份程式只讓一個人吃，範例 2 會 WA——這是正常的，逐筆給分之下子題組 1 的 \(50\) 分穩穩到手。\(L\) 這個陣列滿分解會直接拿來用。

從 50 分到 100 分：DP，但每個右端點只看最長的那一段

多人的時候要決定「誰從哪裡吃到哪裡」，用 DP：

\(dp[p][j]\) ＝ 只考慮前 \(j\) 攤、至多用 \(p\) 個人，最多能造訪幾攤。

第 \(j\) 攤只有兩種情況：

1. 沒有人造訪第 \(j\) 攤：\(dp[p][j] = dp[p][j - 1]\)。
2. 某個人的路線在第 \(j\) 攤結束：他從第 \(l\) 攤開始，這一段要合法就得 \(L[j] \le l \le j\)；前面 \(l - 1\) 攤交給剩下 \(p - 1\) 個人，得到 \(dp[p-1][l-1] + (j - l + 1)\)。

把情況 2 的 \(l\) 全部枚舉一遍，一格要花 \(O(j - L[j])\)；品項幾乎不重複時每個區段長達 \(10^5\)，總共 \(n \cdot k \cdot 10^5\)，本站實測超過時限。

砍掉這一刀的觀察：情況 2 只需要看 \(l = L[j]\)，也就是最長的那一段。 假設最佳解裡最後一個人吃的是較短的 \([l', j]\)（\(l' > L[j]\)），把他的起點往左拉到 \(L[j]\)，多吃了 \(l' - L[j]\) 攤；前一個人的路線 \([a, b]\) 若因此和他重疊（\(b \ge L[j]\)），就把前一個人截短到 \([a, L[j] - 1]\)——合法區段的前半段還是合法的，截到空掉也沒關係（那個人乾脆不吃）。前一個人最多少掉 \(b - L[j] + 1\) 攤，而 \(b < l'\)，所以少掉的不會超過多拿的（圖 1）。換句話說，拉長最後一段永遠不會變差，最佳解一定可以長成「最後一段是最長的那段」的樣子。

每一格 \(O(1)\)，整張表 \(O(nk) \le 5 \times 10^6\)。表格 \((k+1)(n+1)\) 個 int 最多約 \(6 \times 10^6\) 個、\(24\) MB，直接開得下。

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

const int MAX_N = 1000005;
const int MAX_A = 100005;
int a[MAX_N], L[MAX_N];
int last[MAX_A];

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];

    int left = 1;
    for (int j = 1; j <= n; j++) {         // 和 50 分版一樣，先算每個 j 的 L[j]
        left = max(left, last[a[j]] + 1);
        last[a[j]] = j;
        L[j] = left;
    }

    // dp[p][j]：前 j 攤、至多 p 個人，最多造訪幾攤（第 0 列、第 0 行都是 0）
    vector<vector<int>> dp(k + 1, vector<int>(n + 1, 0));
    for (int p = 1; p <= k; p++) {
        for (int j = 1; j <= n; j++) {
            int skip = dp[p][j - 1];                          // 第 j 攤沒人吃
            int take = dp[p - 1][L[j] - 1] + (j - L[j] + 1);  // 有人從 L[j] 吃到 j
            dp[p][j] = max(skip, take);
        }
    }
    cout << dp[k][n] << '\n';
    return 0;
}

\(k = 1\) 時第 \(1\) 列就是「以 \(j\) 結尾的最長區段」取前綴最大值，和 50 分版算的是同一件事；範例 2 的 \(dp[3][10] = 8\)。

測過再交：範例沒有「拉長最後一段」的場面

範例 1 是 \(k = 1\)，範例 2 的最佳解三個人剛好首尾相接。沒蓋到的：人比需要的多、品項全部相同、品項 \(0\) 與最大值、以及「每個人都貪最長的一段」會吃虧的局面。

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