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) ]

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