前言
上手难度挺高(我太菜了,我是垃圾,这么简单的结论我想了那么久?)
本题价值 >∑i=14STi>\sum_{i=1}^4 S_{T_i}>∑i=14 STi
题解
大胆猜结论:无脑往单个墙里填大的。
如果没有 wiw_iwi 都是 222 的幂次这个约束的话,上述贪心就不适用了。
比如墙宽度为 777,板子长度分别为 2,2,2,2,3,32,2,2,2,3,32,2,2,2,3,3,你无脑填大的答案是 333,但实际是 222。
我们想证明无脑填大的是不劣的,也就是证明填 111 个大的一定不劣于填 222 个小的。
这个显然,因为 222 的幂次的性质,2k−1+2k−1=2k2^{k-1}+2^{k-1}=2^k2k−1+2k−1=2k,而当前面项的指数变小时式子取到小于号,所以是不劣的。
然后做完了。拿个桶存 wiw_iwi 随便搞即可。
妈的,咋这么简单,我做的时候真不会证,如此状态,如何 S1???