1465 . H遊戲密笈 - EXTREME
TopCoder
Tags
Description
還記得H遊戲密笈（TIOJ 1446）嗎？
你最近又迷上了另一款H遊戲（Heuristic Game，一款能啟發人coding大進步的遊戲）。
但是你最近卡關了，這又讓你覺得很不愉快。
在一次偶然的機會中，你在圖書館發現了一套『H遊戲密笈』，裡面有教你如何破台的方法，因此你迫不及待的想要把那套『H遊戲密笈』借回家。
但不幸的是，那套書是鎮館之寶，是不能外借的，所以你只好靠紙筆把那本『H遊戲密笈』帶回家（抱歉，影印機和打字機都故障了。）。
當然因為全部都自己抄，實在是太累了，你就請了 k 個人來幫你抄，而你自己則在一旁休息。
這套書總共有 m 本，要抄完每一本書所需的時間都不大一樣，而抄書者只能抄連續編號的書。當然，這k個人是可以同時抄的。
請問你要怎麼安排，才能在最短時間內將這套『H遊戲密笈』帶回家呢？
Input Format
本題有多筆測試資料：
第一行有一個數字 T ，代表有 T 筆測試資料
每一筆測試資料有兩行。第一行有兩個正整數 m, k，代表有 m 本書和 k 個人 ( 1 <= k <= m <= 500 )。
第二行有 m 個正整數ai，代表編號 i 的書抄完需要多少時間。( 0 < ai <= 10,000,000)
Output Format
對於每一組測試資料，請輸出一行，為將a1到am分割為k個部分的一個序列，每個部分為一個抄書者所要抄的書。
如果有多種可能的話，請輸出使第一個抄書者抄最少的解，如果相同的話再比較第二個......
但要特別注意的是，如果有人被請來幫忙，卻沒有事情可以做的話，他會很不高興，所以每個人都至少要抄到一本書。
Sample Input 1
2
9 3
100 200 300 400 500 600 700 800 900
5 4
100 100 100 100 100
9 3
100 200 300 400 500 600 700 800 900
5 4
100 100 100 100 100
Sample Output 1
100 200 300 400 500 / 600 700 / 800 900
100 / 100 / 100 / 100 100
100 / 100 / 100 / 100 100
Hints
Problem Source
原TIOJ1465 / 建中校內培訓第四次模擬考試。
Problem Setter：hallogameboy、peter50216
(Adapt From：CEOI 1998)
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 9 |
| 2 | 1 | 9 |
| 3 | 2 | 9 |
| 4 | 3 | 9 |
| 5 | 4 | 9 |
| 6 | 5 | 9 |
| 7 | 6 | 9 |
| 8 | 7 | 9 |
| 9 | 8 | 9 |
| 10 | 9 | 9 |
| 11 | 10 | 10 |