|
|
|
|
背景 Background |
|
|
|
石子合并的三种类型：
一：任意版
有N堆石子，现要将石子有序的合并成一堆，规定如下：每次只能移动任意的2堆石子合并，合并花费为的一堆石子的数量。设计一个算法，将这N堆石子合并成一堆的总花费最小（或最大）。
此类问题比较简单，就是哈夫曼编码的变形，用贪心算法即可求得最优解。即每次选两堆最少的，合并成新的一堆，直到只剩一堆为止。证明过程可以参考哈夫曼的证明过程。
所用的数据结构：
1、 是堆，取两次堆顶的最小元素，相加后再加入堆中，重复n-1次即可。
2、 两个队列，一个是原始的从小到大排序后的石子序列A。
一个合并后的石子生成的序列B，
注意：这两个序列都是有序的（从小到大），总是从它们中取出最小的两个相加到序列B。
二：直线版
在一条直线上摆着N堆石子，现要将石子有序的合并成一堆，规定如下：每次只能移动相邻的2堆石子合并，合并花费为将的一堆石子的数量。设计一个算法，将这N堆石子合并成一堆的总花费最小（或最大）。
如果熟悉矩阵连乘对这类问题肯定非常了解。矩阵连乘每次也是合并相邻两个矩阵（只是计算方式不同）。那么石子合并问题可用矩阵连乘的方法来解决。
那么最优子结构是什么呢？如果有N堆，第一次操作肯定是从n-1个对中选取一对进行合并，第二次从n-2对中选取一对进行合并，以此类推……
设best[i][j]表示i-j合并的最优值, sum[i][j]表示第i堆石子到第j堆石子的总数量，递推公式如下：
F[I,j]=0; (i=j)
F[I,j]=min{f[I,k]+f[k+1,j]}+sum[I,j] (i<>j);
三：圆形版
如果石子是排成圆形，其余条件不变，那么最优值又是什么呢？
因为圆形是首尾相接的，初一想，似乎与直线排列完全成了两个不同的问题。因为每次合并后我们都要考虑最后一个与第一个的合并关系。直线版的矩阵连乘对角线式的最优子结构不见了。f(i, j)表示i-j合并的最优值似乎并不可行，因为我们可以得到的最优值第一步就是第一个与最后一个合并，那么f(i, j)并不能表示这种关系。
修改一下，f(i, j)表示从第i个开始，合并后面j个得到的最优值。sum(i, j)表示从第i个开始直到i+j个的数量和。那么这个问题就得到解决了。注意要把其看成环形，即在有限域内的合并。
破圆化直：将圆形的石子归并化为直线型石子归并。
方法是：将原来的石子长度增加一倍，加在原来的后面，a[1]~a[n],a[1]~a[n],
求从1，2，3，~n开始的n个合并的最小值，最其中一个最小值即可。
#
上面第二类与第三类的代码复杂度都是O（n^3)，n为石子堆数目，那么还有没有复杂度更低的方法呢？有的。也是使用动态规划，由于过程满足平行四边形法则，优化后可以将复杂度降为O（n^2)。
石子合并动态规划思路：
阶段i：石子的每一次合并过程，先两两合并，再三三合并，...最后N堆合并
状态s：每一阶段中各个不同合并方法的石子合并总得分。
决策：把当前阶段的合并方法细分成前一阶段已计算出的方法，选择其中的最优方案
具体来说我们应该定义一个数组s[i,j]用来表示合并方法，i表示从编号为i的石头开始合并，j表示从i开始数j堆进行合并，s[i,j]为合并的最优得分。
对于上面的例子来说，初始阶段就是s[1,1],s[2,1],s[3,1],s[4,1],s[5,1],s[6,1]，因为一开始还没有合并，所以这些值应该全部为0。
第二阶段：两两合并过程如下，其中sum(i,j)表示从i开始数j个数的和
s[1,2]=s[1,1]+s[2,1]+sum(1,2)
s[2,2]=s[2,1]+s[3,1]+sum(2,2)
s[3,2]=s[3,1]+s[4,1]+sum(3,2)
s[4,2]=s[4,1]+s[5,1]+sum(4,2)
s[5,2]=s[5,1]+s[6,1]+sum(5,2)
s[6,2]=s[6,1]+s[1,1]+sum(6,2)
第三阶段：三三合并可以拆成两两合并，拆分方法有两种，前两个为一组或后两个为一组
s[1,3]=s[1,2]+s[3,1]+sum(1,3)或s[1,3]=s[1,1]+s[2,2]+sum(1,3)，取其最优
s[2,3]=s[2,2]+s[4,1]+sum(2,3)或s[1,3]=s[2,1]+s[3,2]+sum(2,3)，取其最优
第四阶段：四四合并的拆分方法用三种，同理求出三种分法的得分，取其最优即可。以后第五阶段、第六阶段依次类推，最后在第六阶段中找出最优答案即可
|
|
|
|
|
|
|
|
描述 Description |
|
|
|
石子合并：
[问题描述]：
设有n堆石子排成一排，其编号为1、2、3、…、n（n<=100）。每堆石子的数量用：a[1]、a[2]、…、a[n] 表示，现将这n堆石子归并成一堆，归并的规则： ◆每次只能将相邻两堆归并成一堆，即：第 1 堆石子 a[1] 只能与第 2 堆石子 a[2] 归并，最后一堆石子 a[n] 只能与 a[n-1] 归并，中间的石子 a[i] 只能与 a[i-1] 或 a[i+1] 归并； ◆每次归并的代价是两堆石子的重量之和。
例如：假设有这样7堆石子，各堆石子的数量分别是：13 7 8 16 21 4 18，将它们归并成一堆有多种归并方法，下图表示了其中两种归并方法：
13 7 8 16 21 4 18 13 7 8 16 21 4 18
\ / \ / \ / / \ \ / \ / \ /
20 24 25 / \ 15 37 22
\ / / / \/ \ /
44 / / 28 \ /
\ / / \ 59
69 / \ /
\ / \ /
87 87
图A 图B
图a所示归并方式的总代价为：20+24+25+44+69+87=267
图b所示归并方式的总代价为：15+27+22+28+59+87=248
由此可见，不同的归并方式所得到的总代价是不一样的。那么当给出了n堆石子的数量之后，求出合并石子的最小总代价。
|
|
|
|
|
|
|
|
输入格式 Input Format |
|
| |
输入格式
第一行一个整数 n，表示有 n 堆石子；
第二行有n个整数，表示每堆石子的个数(注：每堆石子数<200)；
|
|
|
|
|
|
|
|
输出格式 Output Format |
|
| |
输出格式
第一行一个整数，表示合并的最小代价；
|
|
|
|
|
|
|
|
时间限制 Time Limitation |
|
|
|
各个测试点1s
|
|
|
|
|
|
|
|
|
Flag |
|
题号 |
P1221 |
|
其它 |
通过 |
2人 |
提交 |
4次 |
通过率 |
50% |
难度 |
3 |
|
|
|
|
|
|
