最小m段和问题

最小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;  
} 

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注