h117: 美食博覽會(時限放寬版)
Tags : 2021年9月 APCS DP 二維DP 背包問題
Accepted rate : 28人/37人 ( 76% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-01-24 18:05

Content

注意:這題放寬了g278時限,題目完全相同。

題敘來自g278:

在一個美食博覽會上,有 n 個攤位在販售美食,已知每個攤位只會販售一種美食,且他們販售的美食依序是 a1,a2,…,an,其中可能會有某些攤位販售相同種類的美食。


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

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

 

測資範圍:

對於所有測資:n,k( 1 ≤ ≤1e6, 1 ≤ ≤ 20,1 ≤ × ≤ 5e6 )

subtask 1(50%): k = 1,也就是剛好有個試吃員

subtask 2(50%): 無其他限制

Input

第一行輸入兩個正整數 n,k,代表有 n 個攤位和 k 個試吃員。

接下來有 n 個數字代表每個攤位各別賣哪一種美食,(1 ≤ 種類編號ai ≤ 1e5)

 

Output

 輸出一個正整數,代表試吃員最後吃到的攤位總和最大值。

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
Sample Input #3
2 2
1 2
Sample Output #3
2
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (10%): 2.0s , <10M
公開 測資點#1 (10%): 2.0s , <10M
公開 測資點#2 (10%): 2.0s , <10M
公開 測資點#3 (10%): 2.0s , <10M
公開 測資點#4 (10%): 2.0s , <1M
公開 測資點#5 (10%): 1.0s , <10M
公開 測資點#6 (10%): 1.0s , <10M
公開 測資點#7 (10%): 1.0s , <10M
公開 測資點#8 (10%): 1.0s , <10M
公開 測資點#9 (10%): 1.0s , <10M
Hint :

當時考試時限為1秒但Python為4秒,而g278原題時限太緊,因此這裡對於k!=1提供2秒時限,對於Python較友善(考量judge差異可2s*3=6s),而測資為隨機產生,有誤請告知!!

Tags:
2021年9月 APCS DP 二維DP 背包問題
出處:
2021年9月APCS [管理者:
ktlai@cmgsh.... (賴楷宗)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」