动态规划 切割钢管
有这样一道动态规划的题目：一根N米长的钢管拿去切割，切割多少米的钢管收费多少钱。比如一根10米长的钢管，分别在，2,4,7米出进行切割。第一下在2米处切，收费10元，第二下在四米处切，收费8元（第一下切掉了两米，剩下8米所以收8元），第三下收费6元，一共10+8+6=24元。假如按照4,2,7的顺序，收费10+4+6=20元。求N米长的钢管切割M次的最便宜切法。 动态规划
[解决办法]
这题不是DP类型的，因为切割处只能被切一次，即当前状态的选择得参考前面状态的选择。
提供一个贪心的算法，还没有做证明。
1. 构造模型：对于n米长的钢管在x米处切一刀可以产生x米和n-x米的两根钢管，继续在对应处切，可以将整个钢管切成m份且它们顺序排列，我们现令它们的长度分别为：N0,N1,...Ni,..Nm。
2. 我们逆向思考，通过合理的顺序把它们组合起来合成一根n米长的钢管。
3. 使用贪心算法，每次顺序选择当前两根钢管长度和最小的进行组合，合成一根钢管。
例子：对于要在2,4,7米处进行切割，我们可以得到最后4根钢管的长度分别为：2,2,3,3。
1-> 选择前两根钢管组合，得到4米长的钢管，4,3,3
2-> 选择最后两根钢管组合，得到6米长的钢管，4,6
3-> 最后将两根钢管组合得到10米长的钢管，10
产生的代价为：4+6+10 = 20。
时间复杂度：o(m^2)，如果使用一些数据结构可以达到o(mlgm)。
[解决办法]
这题贪心即可，http://www.51nod.com/question/index.html#!questionId=105，用个优先队列来做。
