题目大意：N个数排成一列，不改变其顺序的将其分成不超过K组，每组至少要含有L个数。现从左到右数过去第i组的值为其含有的所有数的和，与i的乘积。要求将所有分出的组的值加起来的权值最小。DP方程可以简单的这么列：f(i,j)=min{f(i-1,k)+i*(s(i) - s(k))} , 0<=k<=j-Lf(i,j)表示前j个数分成i组的ans。整理一下 ：f(i,j) = min{f(i - 1, k) - i * s(k)} + i * s(i) , 0<=k<=j-L记g(j) = min{f(i - 1, k) - i * s(k)}, 0<=k<=j-L则g(j + 1)和g(j)有递归关系，这样f(i,j)在状态转移的时候就可以在O(1)内完成了。需要注意的是初始化问题和边界问题。感谢：http://acm.hust.edu.cn/thx/problem.php?id=1351
转载于:https://www.cnblogs.com/litstrong/archive/2010/05/26/1744695.html
相关资源：数据结构—成绩单生成器