2016THUPC - I

gistfile1.txt

(by lydrainbowcat)

题意：
给定N个整数a1,a2...an，求1~n的一个排列p1~pn，最大化 abs(abs(abs(abs(a[p1]-a[p2])-a[p3])-a[p4])......-a[pn])。
N<=200, |ai|<=1000

解法：
首先，所有<=0的ai放在最后，可以全部利用起来，使答案不断变大。
于是只需考虑正的ai。找到其中最大的，放在最后，问题变为对于剩余的数做最小化的上述问题。
最小化就比较好做了，相当于把数分成两堆，使得他们的和尽量接近，可以用背包求解。
复杂度O(N*Σ|ai|)

证明：
引理1：把一些正整数数分成两堆，两堆数的和的差，就是上述嵌套绝对值差式子的最小化解。
由于这些数都必须用，所以通过背包使得两堆的和最接近，显然是一个下界。
然后我们可以构造出一个这样的解：假设最后的解是A堆减去B堆的绝对值，初始化序列为空，sum=0，如果当前sum非负，就从B堆取一个放在序列末尾，sum减掉该数；如果sum为负，就从A堆取一个放在序列末尾，sum加上该数。最后按照这个序列的顺序构成上述嵌套绝对值差，展开后就等价于对sum的上述操作。

引理2：在最大化一些正整数构成上述嵌套绝对值差的式子的问题中，答案不会超过最大数的大小。
结论显然。

引理3：在最大化一些正整数构成上述嵌套绝对值差的式子的问题中，把最大数放在最后不会比放在前面更差。
假设最大数是M，放在最后时，其它数按照上述方法构成A,B两堆，两堆的和的差值最小是D，此时答案为M-D。
任取一非最大数P<M，假设P在最后。
若P之前的数做嵌套绝对值差运算，得到的结果<=P，则该结果还是应该最小化。而交换P,M最多使得A,B两堆的和一共变化M-P，故其差的最小值至多向0靠近M-P。而P相比M也变小了M-P，二者相减，不会比M放最后更优。
若P之前的数做嵌套绝对值差运算，得到的结果R>P（由引理2也有R<=M），则该结果应该最大化，答案应为R-P。此时我们可以考虑关于任意子集中的整数做该最大化问题，对子集大小做一归纳，假设除去P以外的数的最大化解R中，M在最后，去掉末尾的M可还原为M-R，加入P会变为|M-R-P|，再加入M就是M-|M-R-P|，去掉绝对值无论得到(M-R)+(M-P)，还是(M-M)+(R+P)，都比P在末尾的R-P更大。
（求更简便证法……）