本文共 1467 字,大约阅读时间需要 4 分钟。
/**********************************************************************************************
Description 给定N个整数组成的序列,现在要求将序列分割为M段,每段子序列中的数在原序列中连续排列。如何分割才能使这M段子序列的和的最大值达到最小? 编程任务:给定N个整数组成的序列,编程计算该序列的最优M段分割,使M段子序列的和的最大值达到最小。 Input 输入的第一行有2个正整数N和M。正整数N是序列的长度;正整数M是分割的断数。接下来的一行中有N个整数。 Output 输出一行即:M段子序列的和的最大值的最小值。 Sample Input 1 1 10 Sample Output 10 Hint 样例二: 输入: 9 3 9 8 7 6 5 4 3 2 1 输出: 17 **********************************************************************************************/
最小m段问题,比较经典动态规划问题,状态转移方程:state[i][j] = min{max{state[i][1]-state[k][1],state[k][j-1]}}
这里state[i][j]表示前i个数据分成j段得最大最小值,state[i][1]表示前i个数据分成1段的值,这里其实就是前i个数据之和。
1 2......k......i 这里可以这样理解,前k个数据的j-1分段的值与k----i的值的最大值,其中k----i的值就是上面state[i][1]-state[k][1]的值。
#include <iostream>
using namespace std; const int MAX_COUNT = 100; int state[MAX_COUNT][MAX_COUNT]; int a[MAX_COUNT]; int MinSum(int n,int m) { int i = 0, j = 0, k = 0, temp = 0, MaxInt; for (i = 1;i <=n;++i) { state[i][1] = state[i-1][1] + a[i]; } for (j = 2;j <=m;++j) { for (i = j; i <= n;++i) { temp = 10000000; for (k = j;k<i;++k) { MaxInt = max(state[i][1]-state[k][1],state[k][j-1]); if (temp > MaxInt) { temp = MaxInt; } } state[i][j] = temp; } } return state[n][m]; } int main() { int n = 0, m = 0; int i = 0,j = 0,k = 0; int temp = 0; int maxint = 0; while (cin >> n && n) { cin>>m; memset(a,0,sizeof(a)); for (i = 1; i <=n;++i) { cin>>a[i]; } memset(state,0,sizeof(state)); cout<<MinSum(n,m)<<endl; } return 0; }转载地址:http://svrvb.baihongyu.com/