h117.
美食博覽會(時限放寬版)
內容
注意:這題放寬了g278時限，題目完全相同。
題敘來自g278:
在一個美食博覽會上，有 n 個攤位在販售美食，已知每個攤位只會販售一種美食，且他們販售的美食依序是 a1,a2,…,an，其中可能會有某些攤位販售相同種類的美食。
國王及大臣們總共 k 人要依序品嚐所有美食，已知每位品嚐員會選擇一段連續的攤位進行試吃，而每個人都不想要試吃到同一種自己曾經吃過的美食，因此一位品嚐員所選到的範圍不能有同一種美食重複出現。另外，品嚐員們都不喜歡被別人打擾用餐，所以任意兩個品嚐員所選到的連續區間必須是沒有重疊的。
給你 n 和 k，以及這 n 個攤位分別販售的美食編號，請計算出這些試吃員們總共最多可以吃到幾攤的美食？
測資範圍:
對於所有測資:n,k( 1 ≤ n ≤1e6, 1 ≤ k ≤ 20,1 ≤ n × k ≤ 5e6 )
subtask 1(50%): k = 1，也就是剛好有個試吃員
subtask 2(50%): 無其他限制
輸入說明
第一行輸入兩個正整數 n,k，代表有 n 個攤位和 k 個試吃員。
接下來有 n 個數字代表每個攤位各別賣哪一種美食，(1 ≤ 種類編號ai ≤ 1e5)
輸出說明
輸出一個正整數，代表試吃員最後吃到的攤位總和最大值。
範例輸入
#1
5 1 1 2 1 3 1
範例輸出
#1
3
範例輸入
#2
10 3 1 7 1 3 1 4 4 2 7 4
範例輸出
#2
8
範例輸入
#3
2 2 1 2
範例輸出
#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
公開 測資點#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
提示 ：
當時考試時限為1秒但Python為4秒，而g278原題時限太緊，因此這裡對於k!=1提供2秒時限，對於Python較友善(考量judge差異可2s*3=6s)，而測資為隨機產生，有誤請告知!!
出處:
2021年9月APCS
[管理者：
ktlai@cmgsh.
...
(賴楷宗)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||