作者ddavid (谎言接线生)
看板Prob_Solve
标题Re: [问题] 乌龟塔问题
时间Fri Mar 8 01:53:24 2019
※ 引述《nicknick0630 (NICK)》之铭言：
: 乌龟塔问题 :
: 有 N 只乌龟，第 i 只重 Wi 克且有 Si 的力量，代表他可以负载 Si - Wi 的重量在背上
: 求由这 N 只乌龟可以叠出的最大高度?
假设已知正确答案叠出了高度m，由上而下所有重量与力量如下：
重量 W1 W2 ... W(m-1) Wm
力量 S1 S2 ... S(m-1) Sm
考虑其中某一层k，依题意，他的力量能够撑起包括自己在内的上层所有重量：
Sk >= W1 + W2 + ... + W(k-1) + Wk
假设k这只事实上比他上一层(k-1)那只力量还小：
S(k-1) > Sk
得到：
S(k-1) > Sk
>= W1 + W2 + ... + W(k-1) + Wk
发现其实(k-1)这只也可以抬得动这k层全部的重量。另外：
Sk >= W1 + W2 + ... + W(k-2) + W(k-1) + Wk
> W1 + W2 + ... + W(k-2) + Wk
理所当然地，k当然也抬得动这k层少了(k-1)那只的重量。
也就是说原本的排序：
1 2 ... (k-1) k ... m
改成：
1 2 ... k (k-1) ... m
也就是这两层对调也不会有任何问题，k跟(k-1)都还是抬得动。
因此，每当相连的上层比下层有力时，把这两层对调一定不会发生问题。反覆这
样的操作，我们必然可以将顺序调整成下层比上层有力而仍然不发生问题（可经由泡
沫排序法实际操作得到），因此必然存在一组最佳解是力量可以依序由上而下刚好是
由小到大，而这组解可由力量排序的DP得到。
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 114.36.170.251
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1551981206.A.57E.html
1F：推 nicknick0630: 谢谢大大精辟的解说 03/08 09:45
2F：推 nicknick0630: 那请问大大 可以用通则的方式来证明用重量排序去算 03/08 09:50
3F：→ nicknick0630: 答案会是错的吗？ 因为我只会举范例但想不太到怎麽 03/08 09:50
4F：→ nicknick0630: 证明 03/08 09:50
反例有绝对的命题推翻效果，不需要额外进行推导。
如果是想要推导反例的通则可以自己试看看啦。
5F：推 ckc1ark: 有反例就算是证明了 03/08 10:26
6F：推 cutekid: 推 d 大详细说明 03/08 11:30
※ 编辑: ddavid (114.36.170.251), 03/09/2019 03:20:52