ZJU/ZOJ 1995 Spiderman 解题报告

题目大意是给出n个数，可以对这n个数进行加减操作，使最后的值为0，要求操作过程中值必须始终为非负数，求使操作过程中出现过的最大值最小的操作方案。

DP的思路类似ZJU/ZOJ 2059，将所有符号为负的数移到等式右边，实际上就变成了求两个和相等的数列。很明显如果sum为奇数则必定无解。类似的，DP过程中如果高度差大于mid则必定是无效状态。只不过这题多了一个限制条件，要求操作过程中始终非负，同时要求记录操作方案。因此本题就不能使用滚动数组的优化了。

3026661 2008-08-07 16:08:48 Accepted 1995 FPC 00:00.01 496K IwfWcf@LZOI