# APCS實作題2021年9月第4題：美食博覽會

> 日期：2024年8月23日
> 作者：王一哲
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=g278)
> [ZeroJudge 題目連結（時間放寬版）](https://zerojudge.tw/ShowProblem?problemid=h117)

## 題目

### 問題描述

在一個美食博覽會上，有 $n$ 個攤位在販售美食，已知每個攤位只會販售一種美食，且他們販售的美食依序是 $a_1, a_2, \dots, a_n$，其中可能會有某些攤位販售相同種類的美食。

國王及大臣們總共 $k$ 人要依序品嚐所有美食，已知每位品嚐員會選擇一段連續的攤位進行試吃，而每個人都不想要試吃到同一種自己曾經吃過的美食，因此一位品嚐員所選到的範圍不能有同一種美食重複出現。另外，品嚐員們都不喜歡被別人打擾用餐，所以任意兩個品嚐員所選到的連續區間必須是沒有重疊的。

給你 $n, k$，以及這 $n$ 個攤位分別販售的美食編號，請計算出這些試吃員們總共最多可以吃到幾攤的美食？
<br />

### 輸入說明

第一行輸入兩個正整數 $n, k~(1 \leq n \leq 10^6,~ 1 \leq k \leq 20,~ 1 \leq n \times k \leq 5 \times 10^6)$，代表有 $n$ 個攤位和 $k$ 個試吃員。

接下來有 $n$ 個數字代表每個攤位各別賣哪一種美食，$a_1, a_2, \dots, a_n~ (1 \leq a_i \leq 10^5)$。

配分
- 50%：$k = 1$
- 50%：無其它限制
<br />

### 輸出說明

輸出 $k$ 個試吃員總共最多可以吃到幾個攤位。
<br />

### 範例輸入1

5 1
1 2 1 3 1

### 範例輸出1

3

<br />

### 範例輸入2

10 3
1 7 1 3 1 4 4 2 7 4

### 範例輸出2

8

<br />

## Python 程式碼

從吳邦一教授的 APCS 解題影片〈[PyAp45 Python APCS 題解：美食博覽會(AP202109_4), ZeroJudge 編號 g278.](https://youtu.be/6ON6VyRTV2Q?si=3HsDn8K-snt81gZh)〉中看到的寫法。在原版題目下，第10筆測資開始超時。在時限放寬版，第2筆測資開始超時。

n, k = map(int, input().split())  # 讀取攤位數量 n，人數 k
stall = [0] + list(map(int, input().split()))  # 讀取攤位資料，最左側加上 0
left = [0]*(n+1)  # left[i] 為第 i 個攤位為終點，最左側的起點，[left[i], i] 區間沒有重複的食物
last = [0]*100001  # last[x] 為第 x 種食物最後一次出現的位置，題目限制最多有 100000 種食物

"""
 第1部分：用滑動視窗找不重複的區間
 每次由 i 向右滑到 i+1，如果 stall[i+1] 不在 [left[i], i] 區間內，left 不同，即
 left[i+1] = left[i]；如果 stall[i+1] 在 [left[i], i] 區間內，移動 left，即 left[i+1] = last[stall[i+1]] + 1；
 取 left[i] 及 last[stall[i+1]]+1 較右側者，即 left[i+1] = max(left[i], last[stall[i+1]]+1)
"""
for i in range(1, n+1):  # 掃過第 1 ~ n 個攤位
    left[i] = max(left[i-1], last[stall[i]]+1)  # 更新 left
    last[stall[i]] = i  # 更新 last
"""
 第2部分：用滾動陣列找 k 個人
 f(j, i) 是在第 i 個攤位前選 j 個區間的最長總和，j 最後要等於 k
 1. 沒有取任何區間 j = 0 或是沒有任何攤位 i = 0，f(j, i) = 0
 2. 第 i 個攤位不在解之中，f(j, i) = f(j, i-1)
 3. 第 i 個攤位在解之中，最後一個區間是以 i 為終點，向左端越遠越好，即 left[i] 左側要取 j-1 個區間，遞迴式為
    f(j, i) = f(j-1, left[i]-1) + (i - left[i] + 1) ，第二項為 [left[i], i] 區間長度 
"""
p = [0]*(n+1)  # 滾動陣列，現在的解
d = [0]*(n+1)  # 滾動陣列，前一個解
for j in range(k):  # k 個人，執行 k 次
    for i in range(1, n+1):  # 掃過第 1 ~ n 個攤位
        p[i] = max(p[i-1], d[left[i]-1]+i-left[i]+1)  # 第一項為第 i 個攤位不在解之中，第二項為第 i 個攤位在解之中
    p, d = d, p  # 交換
print(d[n])  # 印出答案

<br /><br />

## C++ 程式碼

在原版題目下，費時最久約為 0.1 s，使用記憶體最多約為 16 MB，通過測試。在時限放寬版，費時最久約為 0.2 s，使用記憶體最多約為 16 MB，通過測試。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, k; cin >> n >> k;  // 讀取攤位數量 n，人數 k
    vector<int> stall (n+1, 0);
    for(int i=1; i<=n; i++) cin >> stall[i];  // 讀取攤位資料，最左側加上 0
    vector<int> left (n+1, 0);  // left[i] 為第 i 個攤位為終點，最左側的起點，[left[i], i] 區間沒有重複的食物
    vector<int> last (100001, 0);  // last[x] 為第 x 種食物最後一次出現的位置，題目限制最多有 100000 種食物

    /* 第1部分：用滑動視窗找不重複的區間
     * 每次由 i 向右滑到 i+1，如果 stall[i+1] 不在 [left[i], i] 區間內，left 不同，即
     * left[i+1] = left[i]；如果 stall[i+1] 在 [left[i], i] 區間內，移動 left，即 left[i+1] = last[stall[i+1]] + 1；
     * 取 left[i] 及 last[stall[i+1]]+1 較右側者，即 left[i+1] = max(left[i], last[stall[i+1]]+1) */
    for(int i=1; i<=n; i++) {  // 掃過第 1 ~ n 個攤位
        left[i] = max(left[i-1], last[stall[i]]+1);  // 更新 left
        last[stall[i]] = i;  // 更新 last
    }
    
    /* 第2部分：用滾動陣列找 k 個人
     * f(j, i) 是在第 i 個攤位前選 j 個區間的最長總和，j 最後要等於 k
     * 1. 沒有取任何區間 j = 0 或是沒有任何攤位 i = 0，f(j, i) = 0
     * 2. 第 i 個攤位不在解之中，f(j, i) = f(j, i-1)
     * 3. 第 i 個攤位在解之中，最後一個區間是以 i 為終點，向左端越遠越好，即 left[i] 左側要取 j-1 個區間，遞迴式為
          f(j, i) = f(j-1, left[i]-1) + (i - left[i] + 1) ，第二項為 [left[i], i] 區間長度  */
    vector<int> p (n+1, 0), d (n+1, 0);  // 滾動陣列，現在的解，前一個解
    for(int j=0; j<k; j++) {  // k 個人，執行 k 次
        for(int i=1; i<=n; i++)  // 掃過第 1 ~ n 個攤位
            p[i] = max(p[i-1], d[left[i]-1]+i-left[i]+1);  // 第一項為第 i 個攤位不在解之中，第二項為第 i 個攤位在解之中
        swap(p, d);  // 交換
    }
    cout << d[n] << "\n";  // 印出答案
    return 0;
}

<br /><br />

---

###### tags:`APCS`、`Python`、`C++`