感覺不是窮舉組合，因為每隊人數要相同，也許 greedy 就行了。

感覺不是窮舉組合，因為每隊人數要相同，也許 greedy 就行了。

用什麼條件 $\text{Greedy}$ ?

我自己是寫窮舉，可是需要做一些剪枝操作，複雜度 $O(\frac{N!}{K!P!})$，$P$ 是每隊人數。

$N!$ 窮舉
$÷K!$ 不窮舉組的排列
$÷P!$ 不窮舉人的排列

目前他人上傳的代碼看起來都是少了 $÷K!$ 導致超時。

我猜官解應該差不多就是這樣啦，這樣 $N=15$ 複雜度是合理的，可是 $N=16$ 就會超時（多了約 $20$ 倍）

挺好奇你的 $\text{Greedy}$ 是怎麼寫的，等你上傳我再來 hack 看看🤪🤪🤪

我自己是寫窮舉，可是需要做一些剪枝操作，複雜度 $O(\frac{N!}{K!P!})$，$P$ 是每隊人數。

$N!$ 窮舉
$÷K!$ 不窮舉組的排列
$÷P!$ 不窮舉人的排列

目前他人上傳的代碼看起來都是少了 $÷K!$ 導致超時。

我猜官解應該差不多就是這樣啦，這樣 $N=15$ 複雜度是合理的，可是 $N=16$ 就會超時（多了約 $20$ 倍）

更正

複雜度是
$O(\frac{N!}{P{!}^{K}K!})$

這樣應該要到 $N=18$ 才會爆

我自己是寫窮舉，可是需要做一些剪枝操作，複雜度 $O(\frac{N!}{K!P!})$，$P$ 是每隊人數。

$N!$ 窮舉
$÷K!$ 不窮舉組的排列
$÷P!$ 不窮舉人的排列

目前他人上傳的代碼看起來都是少了 $÷K!$ 導致超時。

我猜官解應該差不多就是這樣啦，這樣 $N=15$ 複雜度是合理的，可是 $N=16$ 就會超時（多了約 $20$ 倍）

 

更正

複雜度是
$O(\frac{N!}{P{!}^{K}K!})$

這樣應該要到 $N=18$ 才會爆

我想錯了。

本來會有 greedy 的念頭是因為

這題是求 分組和的最大乘積

以為只要把每組和的差距盡量縮小即可。 

這想法顯然不切實際.