Re: [今天我们思考21]DPDP（二）

[dd_engi]

> DD，你在解题报告里面说这道题没人AC，你觉得原因是什么？
原因是……一开始我的测试数据有问题，事实上是有两个人AC的。另外，很多DP题，包括这个，在编码实现时，边界条件的设定需要仔细考虑，这个题不少人
没AC就是因为这个。

On 5月20日, 上午10时49分, pongba <pon...@gmail.com> wrote:
> 2008/5/20 dd_engi <tianyi...@gmail.com>:
>
> > 就是这样嘛，没什么复杂的，似乎也没更好的方法。
>
> DD，你在解题报告里面说这道题没人AC，你觉得原因是什么？
>
> --
> 刘未鹏(pongba)|C++的罗浮宫http://blog.csdn.net/pongba
> TopLanguagehttp://groups.google.com/group/pongba

[Lee MaRS]

2008/5/20 pongba <pon...@gmail.com>:
> 手头没有笔，躺在椅子上琢磨了一会（没有纸笔很是痛苦，想到后面的，前面的就从脑袋里消失了，尤其是当前后两种想法没有太大联系的时候）。
>
> 一开始，被你的"不常见"误导了，走了一个弯路，想通过对搜索空间的分类讨论来对问题降阶：即，考虑其中一个塔的可能性，这个塔实际上就是原序列的一个子序列。立即想到经典的按照序列的结尾元素分类讨论。但要想证明最优子结构似乎有点复杂。手头没纸笔，就先搁下了。
>
> 然后回头用另一种简单的思路：直接对问题的限制参量降阶。说白了也就是直接考虑n-1阶子问题。发现是可行的：最高双子塔要么需要用到最后一个元素（最后一块积木），要么不需要用到。如果不需要用到a[n]，那么问题就降为求a[1..n-1]下的最高双子塔。如果需要用到，问题就降为求a[1..n-1]下所有双塔高度差为a[n]的最高双子塔（一个双塔相差k的双子塔的高度以较高的那个来计）。考虑到原问题实际上也就是求a[1..n]下的双塔高度差为0的最高双子塔。所以只要建立a[1..i]下双塔高度差为k的最高双子塔f(i,
> k)的递归关系即可：
>
> f(i,k) = max(f(i-1, k), f(i-1, |k+a[i]|), f(i-1, |k-a[i]|) + min(k, a[i]));
>
> 平凡情况是：
>
> f(0,0) = 0;
> f(0,k) = INT_MIN; where k!=0
>
> 子问题结果的缓存有点麻烦，因为k的可能值并非线性的，而是组合的。看起来用hash可以。或者让k从0滑动到sigma(a[i]); i = 0..n
> 这个代价就太大了。还有更好的办法吗？

恩，基本上就是这样了。:-)

注意到题目里面已经说过sigma(a[i]) < 2000。整体复杂度已经可以接受了。

另外这道题更适合用从初态出发外推式计算，更易于思考。对于k，直接枚举即可。或者可以用两个队列，分别维护当前阶段的有效状态，以及下一阶段的有效状态。有点BFS的感觉。:-)

>
> 2008/5/20 Lee MaRS <lee...@gmail.com>:
>>
>> 动态规划的一大要点就是状态的设计，这个除了靠灵光一闪，多积累点经验也是很有必要的。
>>
>> 帖点算法书上不常见的状态设计的题目：
>>
>> [双子塔]
>> 五岁大的Rosie决定用她收集的积木搭建一个最高的双子塔（两个塔当然得高度一样）。问她最多能搭出多高的双子塔？
>>
>> 输入
>> N(N<100)表示积木的数目，H[1..N]分别表示N块积木的高度。所有的积木的高度总和不超过2000。不要求用上所有的积木。
>>
>> 输出
>> 能搭出的最大高度。如果不存在这样的方案，输出Sorry
>>
>> 原题在这里
>> http://acm.zju.edu.cn/show_problem.php?pid=2059
>
>
>
> --
> 刘未鹏(pongba)|C++的罗浮宫
> http://blog.csdn.net/pongba
> TopLanguage
> http://groups.google.com/group/pongba
> >
>