g278: 4. 美食博覽會
Tags : APCS
Accepted rate : 76人/104人 ( 73% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-09-06 18:41

Content

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


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

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

Input

第一行輸入兩個正整數 $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%) 無其它限制
Output

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

Sample Input #1
5 1
1 2 1 3 1
Sample Output #1
3
Sample Input #2
10 3
1 7 1 3 1 4 4 2 7 4
Sample Output #2
8
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (5%): 1.0s , <10M
公開 測資點#1 (5%): 1.0s , <10M
公開 測資點#2 (5%): 1.0s , <10M
公開 測資點#3 (5%): 1.0s , <10M
公開 測資點#4 (5%): 1.0s , <10M
公開 測資點#5 (5%): 1.0s , <10M
公開 測資點#6 (5%): 1.0s , <10M
公開 測資點#7 (5%): 1.0s , <10M
公開 測資點#8 (5%): 1.0s , <10M
公開 測資點#9 (5%): 1.0s , <10M
公開 測資點#10 (5%): 1.0s , <10M
公開 測資點#11 (5%): 1.0s , <10M
公開 測資點#12 (5%): 1.0s , <10M
公開 測資點#13 (5%): 1.0s , <10M
公開 測資點#14 (5%): 1.0s , <10M
公開 測資點#15 (5%): 1.0s , <10M
公開 測資點#16 (5%): 1.0s , <10M
公開 測資點#17 (5%): 1.0s , <10M
公開 測資點#18 (5%): 1.0s , <10M
公開 測資點#19 (5%): 1.0s , <10M
Hint :
Tags:
APCS
出處:
2021年9月APCS [管理者:
cthbst (吳宗達)
]


ID User Problem Subject Hit Post Date
27078
r1cky (APCS實作兩級分)
g278
Java 解題心得
74 2021-09-12 10:53
27075
cthbst (吳宗達)
g278
本題測試資料
116 2021-09-12 07:59
27025
711004@stu.c... (牟宗晞)
g278
extra
312 2021-09-07 17:25
27008
ck1090758@gl... (peienwu)
g278
小提示
486 2021-09-06 18:59