石头合并问题
日期:2014-05-02 22:20:01
最后更新日期:2015-10-06 10:54:37
在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。
解:
2.圆的问题。对于由五个a[1],a[2],a[3],a[4],a[5]的圆。可以分解为5个分别从a[1]到a[5]起始的序列。像这样:
a[1],a[2],a[3],a[4],a[5]
a[2],a[3],a[4],a[5],a[1]
a[3],a[4],a[5],a[1],a[2]
a[4],a[5],a[1],a[2],a[3]
a[5],a[1],a[2],a[3],a[4]
注:
之前的解法是贪心，贪心的解法可以构造反例证伪。合并到最后就是两两合并，只需要这两个子序列的子问题的整体最优(加在一起最小得分或最大得分)，那么就是问题的解。
定义m[i,j]从第i堆石头块开始，j个堆的序列的最优解。m[i,j]可以表示一个子问题。
sum[i,j]表示第i堆石头块，j个堆的总和。
对于任何n个堆的环，k从1到n-1。状态如下:
m[i,1] = 0
m[i,j] = min { m[i,k]+m[i+k,j-k] } + sum[i,j]
圆的问题就是m[i,5]，i取1,2,3,4,5。
http://www.hnyzsz.net/Article/ShowArticle.asp?ArticleID=735