dianshu1593 于 2018-08-10 23:47:00 发布
本文介绍了一个关于木板切割的问题，要求在给定的切割点位置上以最小费用完成切割。通过对比之前的栅栏维修问题，指出贪心法不再适用，并提出使用动态规划的方法，定义状态d(i, j)表示切割点i到j的最优费用。文章还简述了该动态规划的实现和时间复杂度。" 80607697,7696813,LoadRunner 分析响应时间,"['性能测试', 'LoadRunner工具', '测试分析'] 一、问题引入
有一根长度为L(L < 1000)的木棍，还有n(n < 50)个切割点的位置（按照从小到大排列）。你的任务是在这些切割点的位置处把棍子切成n+1份，使得总费用最小。每次切割的费用等于被切割的木棍长度。
二、问题分析
这个问题很像前面的栅栏维修（给定n个木棍的长度，切割点任意），这道题目相当于给定n+1个木棍的长度，且切割点固定。之前的贪心法就不能适用，因为用贪心法需要切割的点不一定是给定的切割点。我们必须换一种思路了。
n的规模非常小，可以考虑枚举切割点，但直接枚举所有的切割顺序肯定太大，可以考虑动态规划，枚举切割第一刀的位置。
设d(i,j)为切割小木棍i~j的最优费用，则d(i,j) = min{(d(i,k),d(k,j)) | i < k < j} + a[j] - a[i],其中a[j] - a[i]代表第一刀的费用。
注意，这里i,j都是表示切割点的位置，而不是木棍的序号，这样比较方便。
三、代码实现
1 #include<stdio.h> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 using namespace std; 6 7 const int INF =
