內容
一個村子共有 N 戶人家排在一條直線上，每戶人家擁有不同的財富值Ai，村長有意將全村N戶人家分成連續的M組互助會，但又希望所有戶組中財富總和 T 值最大的一組其 T 值要越小越好，試問此最小可行的 T 值為多少？
以範例 1 為例：N=10, M=2
可以分成 (2, 5, 3, 1, 4)、(2, 3, 6, 1, 4) 兩組，此時最小 T = 2+3+6+1+4 = 16
以範例 2 為例：N=10, M=4
可以分成 (2, 5, 3)、(1, 4, 2, 3)、(6)、(1, 4) 四組，此時最小 T = 2+5+3 = 10
輸入說明
多筆測資( <=100 筆)，每筆測資第一行兩個數字 N、M (1 <= M <= N <= 10000)，代表 N 戶人家分成連續的 M 組，第二行有 N 的整數 Ai (Ai<=10000) 代表各戶的財富值。
輸出說明
每筆測資輸出一行，一個整數代表最小的 T 值。
範例輸入
#1
10 2 2 5 3 1 4 2 3 6 1 4 10 4 2 5 3 1 4 2 3 6 1 4 10 9 2 5 3 1 4 2 3 6 1 4
範例輸出
#1
16 10 6
測資資訊：
記憶體限制：
256
MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 2.0s , <10M
公開 測資點#4 (20%): 2.0s , <10M
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 2.0s , <10M
公開 測資點#4 (20%): 2.0s , <10M
提示 ：
標籤:
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||