1. 阶段数为m.
2. 状态转移方程:
f[i][j]=min max{ f[i][1]-f[k][1],f[k][j-1]}
其中1<=k<i;j<= i <=n; 1<= j <= m;
初态:f[i][1]=f[i-1][1]+a[i]
最优值为f[n][m]。
3. 对于第j阶段中的每个 i, (j<=i <=n),考虑将1到i的序列分为j段子序列,且第j段序列从k开始到i,由最优子结构性质,只需比较第j段序列和第j-1阶段的最优值即可。
决策变量:第j段序列分配i-k个元素
源代码:
测试:9 39 8 7 6 5 4 3 2 1输出17
2010年5月31日11:08:38
posted on 2010-05-31 11:10 bluedream 阅读(3529) 评论(0) 编辑 收藏 引用
Powered by: C++博客 Copyright © bluedream