夏晓光(loveJY)的博客

这个有点难QAQ但是臻大佬切了

$dp_{i,j}$表示选了前i个切糕,然后用了j次优先选择权,那么Tinytree

显然有$dp_{i,0}=1,dp_{i,i}=\frac{\sum_{j=1}^ia_j}{2}$

考虑转移就是当前位置为i

则Kina一定会用一种策略把切糕尽可能均分达到更优效果

所以就是对于$a_i$分为x,y两块满足$(x<y)$,且$max(x+dp_{i-1,j},y+dp_{i-1,j-1})$最小,这样就达到了最优解,注意这里dp值大小是单调的qwq

那么显然可以发现这个能够卡到相等的时候最小,如果不能相等($a_i$不行),我们全部分给小的一方即可

注意我们要先从大到小排序每一块切糕才行QAQ

因为如果先选大的可以逼迫对面做出选择，先选小的给了他更多选择机会就会劣一些