最小m段和问题
时间： 1ms 内存：64M
描述：
给定n 个整数组成的序列，现在要求将序列分割为m 段，每段子序列中的数在原序列中连续排列。如何分割才能使这m段子序列的和的最大值达到最小？
给定n个整数组成的序列,计算该序列的最优m段分割，使m段子序列的和的最大值达到最小。
输入：
输入数据的第1行中有2个正整数n和m。正整数n是序列的长度；正整数m 是分割的段数。
接下来的一行中有n个整数。n≤100。
输出：
输出数据只有一个数，是计算出的m段子序列的和的最大值的最小值。
示例输入：
1 1
10示例输出：
10提示：
参考答案（内存最优[1316]）：
#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
#define INF 1e9
int n,m;
int a[110],f[110][110];
int max(int a,int b)
{
if(a>=b) return a;
else return b;
}
int solve(int n,int m)
{
int i,j,k;
memset(f,0,sizeof(f));
for(i=1;i<=n;++i)
f[i][1]=f[i-1][1]+a[i];
int maxt;
int tmp;
for(i=2;i<=m;++i)
for(j=i;j<=n;++j)
{
tmp=INF;
for(k=i;k<j;++k)
{
maxt=max(f[j][1]-f[k][1],f[k][i-1]);
if(tmp>maxt)tmp=maxt;
}
f[j][i]=tmp;
}
return f[n][m];
}
int main(int argc, char *argv[])
{
cin>>n>>m;
for(int i=1;i<=n;++i)
cin>>a[i];
cout<<solve(n,m)<<endl;
return 0;
}
参考答案（时间最优[0]）：
#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
#define INF 1e9
int n,m;
int a[110],f[110][110];
int max(int a,int b)
{
if(a>=b) return a;
else return b;
}
int solve(int n,int m)
{
int i,j,k;
memset(f,0,sizeof(f));
for(i=1;i<=n;++i)
f[i][1]=f[i-1][1]+a[i];
int maxt;
int tmp;
for(i=2;i<=m;++i)
for(j=i;j<=n;++j)
{
tmp=INF;
for(k=i;k<j;++k)
{
maxt=max(f[j][1]-f[k][1],f[k][i-1]);
if(tmp>maxt)tmp=maxt;
}
f[j][i]=tmp;
}
return f[n][m];
}
int main(int argc, char *argv[])
{
cin>>n>>m;
for(int i=1;i<=n;++i)
cin>>a[i];
cout<<solve(n,m)<<endl;
return 0;
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。