n132. p4. 隊伍分配 - 高中生程式解題系統

內容

　　岳將軍手下有一批士兵，每個人的戰鬥能力不一。下週他們將到戰地執行任務，岳將軍想要把士兵分成數個小隊，每個小隊的人數需相同，並且希望分配後仍擁有優秀的整體戰力。岳將軍評估整體戰力的方式是先計算每個小隊的戰力總和，然後將所有小隊的戰力總和相乘，這個乘積就是整體戰力。
　　舉例來說，如果岳將軍手下有 $4$ 位士兵，戰力分別為 $5$、$8$、$3$、$7$。若岳將軍想把他們分成兩個小隊，則分配方式有下列三種：

小隊一	小隊二	整體戰力
士兵一($5$)、士兵二($8$)	士兵三($3$)、士兵四($7$)	($5+8$)$\times$($3+7$)$\ = 130$
士兵一($5$)、士兵三($3$)	士兵二($8$)、士兵四($7$)	($5+3$)$\times$($8+7$)$\ = 120$
士兵一($5$)、士兵四($7$)	士兵二($8$)、士兵三($3$)	($5+7$)$\times$($8+3$)$\ = 132$

這三種方式中，整體戰力最高的是第三種方法，其整體戰力為 $132$。

　　請撰寫一個程式，給定岳將軍手下士兵的個人戰力以及小隊數目，計算並輸出最高的整體戰力。

輸入說明

　　第一列有兩個整數 $N$ ($1\leq N\leq 15$) 和 $K$ ($1\leq K\leq N$)，代表士兵人數和小隊數，其中 $N$ 必為 $K$ 之倍數。第二行有 $N$ 個正整數，其值均不大於 $100$。同一行的兩個連續整數之間以空白間隔。

輸出說明

　　輸出所有可能的分配情況中，最大的整體戰力值為何？假設此值小於 $2^{63}-1$。

範例輸入 #1

4 2
5 8 3 7

範例輸出 #1

範例輸入 #2

4 4
5 8 3 7

範例輸出 #2

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (5%): 2.0s , <1K
公開測資點#1 (5%): 2.0s , <1K
公開測資點#2 (5%): 2.0s , <1K
公開測資點#3 (5%): 2.0s , <1K
公開測資點#4 (5%): 2.0s , <1K
公開測資點#5 (5%): 2.0s , <1K
公開測資點#6 (5%): 2.0s , <1K
公開測資點#7 (5%): 2.0s , <1K
公開測資點#8 (5%): 2.0s , <1K
公開測資點#9 (5%): 2.0s , <1K
公開測資點#10 (5%): 2.0s , <1K
公開測資點#11 (5%): 2.0s , <1K
公開測資點#12 (5%): 2.0s , <1K
公開測資點#13 (5%): 2.0s , <1K
公開測資點#14 (5%): 2.0s , <1K
公開測資點#15 (5%): 2.0s , <1K
公開測資點#16 (5%): 2.0s , <1K
公開測資點#17 (5%): 2.0s , <1K
公開測資點#18 (5%): 2.0s , <1K
公開測資點#19 (5%): 2.0s , <1K

提示：

標籤:

窮舉

出處:

110 新北市資訊學科能力複賽 [管理者： liaoweichen1024@gmail.com

liaoweichen1 ... (M_SQRT) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」