题意
一个长为L ( L < 1000 ) 的木块， 有n个切割点 分别为c1, c2, c3, ……, cn （0 < ci < L）
每次切割的花费是被切木块的长度 求切割完木块的最小花费思路
区间DP石子归并模板
分析 ： 比赛的时候根本没多想，觉得切木块就是哈夫曼树，各种wr。 第一步和哈夫曼树那个题是一样的，就是要把“切割”看成“合并”倒着往回推，但是，仔细分析一下这个题意中所强调的切割点的坐标，就能发现和哈夫曼树题不一样的地方：选择小木块合并的规则并不是找两个最小木块，而是有“相邻”这一条件限制的！ 区间dp 石子归并 和这个题完全是一样的模型（哭着离开.jpg） N堆石子摆成一条线。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的代价。计算将N堆石子合并成一堆的最小代价。
例如： 1 2 3 4，有不少合并方法 1 2 3 4 => 3 3 4(3) => 6 4(9) => 10(19) 1 2 3 4 => 1 5 4(5) => 1 9(14) => 10(24) 1 2 3 4 => 1 2 7(7) => 3 7(10) => 10(20) 括号里面为总代价可以看出，第一种方法的代价最低，现在给出n堆石子的数量，计算最小合并代价。
是不是吧…完全一样（哭着离开.jpg）…
剩下就是区间dp的递推式了
分治思想：石子归并的最终结果是合并为一堆，所以倒数第二步即是将两堆合并为一堆的过程。所以从后往前看，整个归并过程都是由两堆合为一堆的过程。
dp[ i, j ] 表示合并第 i 堆到第 j 堆所需的最小花费；那么其上一步必然会是由两堆合并设前i~k堆为一堆后k+1~j堆为一堆。所以有f[i][j]=f[i][k]+f[k+1][j]+“(这一步操作需要的)花费” 由题取最小花费即： f[i][j]=min(f[i][j], f[i][k]+f[k+1][j]+“花费”) 预处理出前缀和数组pre[] ( 切木块这个题给的所谓的“切割点坐标”其实就是前缀和了，在最后补一个pre[n+1]=总长即可 ) 那么从i合并到j需要的每步操作需要的花费即pre[j]-pre[i-1] 递推式： f[i][j]=min(f[i][j], f[i][k]+f[k+1][j]+pre[j]-pre[i-1]) 递推：
因为要计算i~j和并的最小代价，所以可选择由最后一堆往前推，假设目前有5堆，则先计算f[5,5],然后f[4,5]直到f[1,5]，而对于f[3,5]时会出现需要f[3,4]与f[4,5]的值，而f[4,5]已经计算过了那么需要计算f[3,4]只需要由i到n枚举区间右边界j，且由i到j枚举分割点k，一个三重循环递推即得：for(int i = n; i >= 1; i-- ) for(int j = i; j <= n; j++ ) for(int k = i; k <= j; k++) dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+pre[j]-pre[i-1]);
预处理好dp[i][j] = i == j ? 0 : INF
做递推即可AC代码
#include#include #include #include #include using namespace std;const int maxn = 55;int l[maxn];int dp[maxn][maxn];const int INF = 0x3f3f3f3f;int main(){ int n, m; while( scanf("%d",&n) == 1 && n ) { scanf("%d",&m); for(int i = 0; i <= m+1; i++) for(int j = 0; j <= m+1; j++) dp[i][j] = i == j ? 0 : INF; for(int i = 1; i <= m; i++) scanf("%d",&l[i]); l[m+1] = n; for(int i = m+1; i >= 1; i-- ){ for(int j = i; j <= m+1; j++ ){ for(int k = i; k <= j; k++){ dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+l[j]-l[i-1]); } } } printf("The minimum cutting is %d.\n", dp[1][m+1]); } return 0;}