65. GY採香蕉

0 Judge

Code: 0


Problem Description

就事實來說,

  1. 演算法賺不到錢
  2. D_site上面有很多好玩的遊戲
  3. 香蕉好吃

基於上述原因,GYLin 最近開始在一個香蕉農場擔任香蕉採收工程師。這份工作的內容主要是將香蕉從樹上摘下來放入袋子中,再將袋子運回倉庫。

農場中有 $N$ 根香蕉,而 GY 總共有 $K$ 個袋子可以用。他發現當兩根香蕉放在同一個袋子時,熟度比較低的香蕉$A$會變得跟熟度比較高的香蕉$B$一樣熟。按照此邏輯,當一堆香蕉放在同一個袋子時,裡面所有香蕉都會變得跟原本袋中最熟的香蕉一樣熟

想當然耳,為了保存得久,採收完的香蕉當然是越不熟越好。GY 已經算出每根香蕉的熟度:一根香蕉的熟度可以用一個正整數表達,而數字越大表示香蕉越熟。而他想請問你,將每根香蕉都裝入其中一個袋子後,最低的總熟度 (每根香蕉的熟度加總) 可以是多少?

Input Format

在每筆測資中只會有兩行,第一行有兩個整數 $N$ $K$ ,分別代表香蕉數量袋子數量。接著在第二行會有 $N$ 個數字 $A_1 … A_N$ ,代表每根香蕉的成熟度。

Input Constraints

$1 \leq N \leq 10^4$

$1 \leq A_i \leq 10^5$

$1 \leq K \leq min(10, N)$

Testcase #1~2 : $N \leq 20$ (score: 20)

Testcase #3~4 : $N \leq 10^4$ (score: 80)

Output Format

輸出一個整數:每根香蕉都放入其中一個袋子後,最小的成熟度加總可以為多少。

Sample IO

Sample In 1

6 2
1 2 1 5 2 5

Sample Out 1

18

Sample In 2

6 3
1 2 1 5 2 5

Sample Out 2

16

Sample In 3

10 3
1 1 1 2 3 4 5 6 7 8

Sample Out 3

47

Sample Exbananation

在第一筆測資,我們可以這樣分配得到最小的成熟度加總:

bag 1 = $\{ 1, 1, 2, 2 \}$

bag 2 = $\{ 5,5 \}$

bag 1 的總熟度為 $2+2+2+2=8$ ,bag 2 任何香蕉的熟度都沒有上升。

在第二筆測資,顯然我們能將同樣成熟度的香蕉分配在一起,達到最小成熟度加總。

在第三筆測資,我們可以這樣分配:

bag 1 = $\{ 1,1,1 \}$

bag 2 = $\{ 2,3,4,5 \}$

bag 3 = $\{ 6,7,8 \}$


Judge Setting

run-time limit: 3000 ms
memory limit: 256000000 byte
測資數量: 4