合并石子问题的算法讨论.pptx

合并石子问题的算法讨论

常州市第一中学田菁曳

例、Anoldstonegame（POJ1738）题目大意有n堆石子（1=n=50000）排在一行，每堆石子给定一个重量。要把n堆石子合并成一堆，每次合并只能将相邻的两堆石子合并成一堆，代价为这两堆石子的重量和，求最小的总代价。

三种算法算法一、朴素区间DP算法算法二、四边形不等式优化DP算法算法三、GarsiaWachs算法

算法一、朴素区间DP算法?

算法二、四边形不等式优化DP算法?

算法二、四边形不等式优化DP算法合并石子问题完全满足以上要求。四边形不等式证明略，详见参考文献。四边形不等式优化普遍能将原本O（n3）复杂度的DP优化到O（n2），是一种比较高效的优化方法。

算法三、GarsiaWachs算法2-递减性质假设第i个石子的权值为a[i]。对于节点k，如果a[k-1]a[k+1]，那么，称节点k满足2-递减性质。

算法三、GarsiaWachs算法GarsiaWachs算法大意：每次寻找最小的一个满足a[k-1]=a[k+1]的k（方便起见设a[0]和a[n+1]等于正无穷），那么我们就把a[k]与a[k-1]合并，之后向前找最大的一个满足a[j-1]a[k]+a[k-1]的j,把合并后的值a[k]+a[k-1]插入a[j]的前面，最后的答案就是每次a[k]与a[k-1]合并的代价和。

算法三、GarsiaWachs算法举例来说：n=6原数列：206101125122061011251220161125122720251237272047371627374784++++=211

算法三、GarsiaWachs算法?正确性证明

算法三、GarsiaWachs算法?

【引理1】???

【引理2】?

【引理2】?

【引理2】?

【引理2】??

【引理3】?

【引理4】?

GarsiaWachs算法实现?

GarsiaWachs算法实现平衡树维护优化对于这个算法，我们只需要维护一个2-递减序列就可以了，算法的精髓在于每次寻找一个最小的k。先把n个数从后往前扫一遍，将不满足2-递减性质的数加进树中，每次更新序列时，通过平衡树来维护，最后算法时间复杂度为O(nlogn)。

总结在证明GarsiaWachs算法的过程中，我们多次用到反证法的思想，通过假设反例成立，推出矛盾来证明，这是一种思想，运用这种思想，能够解决很多正推很难证明的问题。同时，对于一道题目，我们不能总是满足于朴素的算法，而是要尽可能挖掘很多有意义的东西，如果我们努力地钻研，会发现很多意想不到的算法，我们要有努力探索的精神。

欢迎提问。。。谢谢大家！