最小m段和问题 动态规划 c++含讲解

最小m段和问题
给定n个整数组成的序列，现在要求将序列分割为m段，每段子序列中的数在原序列中连续排列。如何分割才能使这m段子序列的和的最大值达到最小？

刚刚写了最大k乘积问题的分析，再过来看这道题，感觉差不多，如果你有兴趣的话，可以看看【动态规划】最大k乘积问题

分析-----美丽的分界线-------
1.问题讲解
5 4 3 2 1 n=5，m=3 5个整数，3段
3段子序列 （5/4/3 2 1，5 4/ 3/ 2 1，5 4 3/2 /1，5/4 3 2 /1）
子序列的和最大：（分别为6，9，12，9）
最大值达到最小即为6
2.代码讲解
solve函数是这道题的关键
f[i][j]:前i个数被分为j段，子序列的和最大值的最小值
t[i]：用来存储数字序列的数组
（1）j=1：不分段
f[i][1]=f[i-1][1]+t[i]; 前i-1个数和+第i个数
（2）j>=2
maxt=max(f[k][j-1],f[i][1]-f[k][1]);
这道题就是将数字序列整体分为两部分，第一部分前k个数分为j-1段，得到子序列的和最大值的最小值，另一部分是最后一段，f[i][1]-f[k][1]：i个数的和-前k个数的和 即为最后一段的和
然后进行比较，得到最大的和
可是呢，还有一个要求，就是要求得到的最大的和是最小的（千万不要绕晕啊，哈哈）
所以用了mint ，通过k的变化，不同的分法，得到的maxt不同，找到最小的，
随着i，j不断增加直至达到n，m即可得到答案啦

#include<bits/stdc++.h>
using namespace std;
void solve(int n,int m,int *t)
{
	int i,j,k,mint,maxt;
	int f[n][m];//n个数分为m段和大值的最小值   5 4/ 3 2 1
		f[0][1]=0; 
	//当j=1  即分为1段时
	for(i=1;i<=n;i++)
	f[i][1]=f[i-1][1]+t[i];
	//当j>=2
	for(j=2;j<=m;j++){//分为j段
		for(i=j;i<=n;i++){//前i个数
			mint=0x3f3f3f;
			for(k=1;k<i;k++){//分割点
				maxt=max(f[k][j-1],f[i][1]-f[k][1]);
				//前k个数分为j-1段得到的和最大值的最小值  最后一段k到i分为一段的和 取max   5 4/ 3 2 1
				if(mint>maxt)
				mint=maxt;//求得到的最大的和是最小的
			}
			f[i][j]=mint;//不同的k划分
		}
	}
	cout<<f[n][m]<<endl;
}
int main()
{
	int n,m;
	cin>>n>>m;
	if(n<m||n==0){
		cout<<0<<endl;
		return 0;
		}
    int t[n];
    for(int i=1;i<=n;i++)
    cin>>t[i];//数字5/4/3 2 1
    solve(n,m,t);
 } 
 

如果看不懂的话，推荐看------>这篇