ZJU/ZOJ 2059 The Twin Towers 解题报告

题目大意是给出n个数，求能否用这n个数组成两个和相等的队列，如果能则输出最大可能的单个队列数字和。

一开始是想着用0/1背包来做的，不过后来发现有bug，虽然x和x/2都有可能取到，但x/2却未必有两份（x表示队列和）。看了相关讨论才想到可以用两个队列的差值进行DP，用f[i,j]表示取到第i个数，队列差为j时的单个队列和最大值，最后输出f[n,0]即可。因为f[i]只与f[i-1]有关，故可以用滚动数组优化空间复杂度。另外有一个效果不错的优化是可以在DP前先将n个数升序排序，这样可以减少DP过程中的枚举量。

3024745 2008-08-06 16:19:51 Accepted 2059 FPC 00:00.21 424K IwfWcf@LZOI