ZJU/ZOJ 1276 Optimal Array Multiplication Sequence 解题报告

题目大意是按照题目所述计算合并n个矩阵花费代价最少的方案。

模型是很经典的石子归并，因为n<=10，所以O(n^3)的朴素DP方法即可AC。而输出方案数可以在DP过程中记录下每次合并的两堆的分割点，递归输出即可。状态转移方程是f[i,j]:=min(f[i,j],row[i,k]*col[k+1,j]*col[i,k]+f[i,k]+f[k+1,j]);(1<=i<j<=n,i<=k<j)。其中f[i,j]表示合并第i到第j个矩阵所花费的最小代价，row[i,j]表示合并第i到第j个矩阵后最优合并方案下的合并后的矩阵的rows值，col[i,j]表示合并第i到第j个矩阵后最优合并方案下的合并后的矩阵的columns值。

3068935    2008-09-13 22:57:30    Accepted    1276    FPC    00:00.00    404K    IwfWcf