g278. 4. 美食博覽會 - 高中生程式解題系統

內容

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

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

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

輸入說明

第一行輸入兩個正整數 $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$ 個數字代表每個攤位各別賣哪一種美食， $(1 \leq a_{i} \leq 10^{5})$

配分

(50%) $k = 1$
(50%) 無其它限制

輸出說明

輸出 $k$ 個試吃員總共最多可以吃到幾個攤位

範例輸入 #1

5 1
1 2 1 3 1

範例輸出 #1

範例輸入 #2

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

範例輸出 #2

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (5%): 2.0s , <10M
公開測資點#1 (5%): 2.0s , <10M
公開測資點#2 (5%): 2.0s , <10M
公開測資點#3 (5%): 2.0s , <10M
公開測資點#4 (5%): 2.0s , <10M
公開測資點#5 (5%): 2.0s , <10M
公開測資點#6 (5%): 2.0s , <10M
公開測資點#7 (5%): 2.0s , <10M
公開測資點#8 (5%): 2.0s , <10M
公開測資點#9 (5%): 2.0s , <10M
公開測資點#10 (5%): 2.0s , <10M
公開測資點#11 (5%): 2.0s , <10M
公開測資點#12 (5%): 2.0s , <10M
公開測資點#13 (5%): 2.0s , <10M
公開測資點#14 (5%): 2.0s , <10M
公開測資點#15 (5%): 2.0s , <10M
公開測資點#16 (5%): 2.0s , <10M
公開測資點#17 (5%): 2.0s , <10M
公開測資點#18 (5%): 2.0s , <10M
公開測資點#19 (5%): 2.0s , <10M

提示：

標籤:

APCS 動態規劃

出處:

2021年9月 APCS [管理者： edison1998402@gmail.com

cthbst (吳宗達) ]

編號	身分	題目	主題	人氣	發表日期
41238	glps1004@gma ... (Ian)	g278	APCS202109全解析	266	2024-07-13 17:11
38937	qerpzzea@gma ... (賽希爾 cecill(陳宥穎))	g278	思路雙指針	583	2024-01-04 21:40
37661	edoctopus322 ... (Moon Jam)	g278	解題思路（含一些小技巧）	792	2023-09-25 19:51
34495	luray0601@gm ... (QWERTYPIG)	g278	C++題解(含想法)	966	2023-03-26 12:34
27369	r1cky (hehe)	g278	測資建議	1418	2021-09-28 09:16