动态规划--斜率优化.doc

动态规划优化_斜率优化先来看一道题(HDU3507):题意:给出N个单词,每个单词有个非负权值Ci,将k个单词排在一行的费用为(Ci)2+M.求最优方案,使得总费用最小.我们很容易得到一个O(N2)的算法:si表示前i个单词的权值和.先写个东西在这:所有元素非负的数组的前缀和值随下标增加单调递增.后面会用到.fi表示将前i个单词排版完毕后的最优值,fi=minfj+(si-sj)2+M.但题目中N的范围是.这个算法明显不行.考虑如何优化.我们固定i,考虑它的两个一般决策点j,k(jk).记gpos=fpos+(si-spos)2+M,即i从pos转移的代价.如果决策点k优于j,那么就有gkgj.展开来:fk+(si-sk)2+Mfj+(si-sj)2+M,化简得fk-fj+sk2-sj2sj,我们在不等式两边除以(sk-sj).不等式化为(fk-f