最小m段和问题.txt

算法设计与分析源代码算法设计与分析源代码

#include<iostream> 
using namespace std; 
void main() 
{ 
int n,m,t,k,tem,o; 
cin>>n>>m; 
int *data=new int [n+1]; 
for(int i=1;i<=n;i++) 
cin>>data[i]; 
int **solve=new int *[n+1]; 
//solve[i][j]代表从第一位到第i位数字分割成j段 
//的最小子段和； 
//此题要求的就是solve[n][m]； 
for(int j=1;j<=n;j++) 
{ 
solve[j]=new int [m+1]; 
} 
solve[1][1]=data[1]; 
for(i=2;i<=n;i++) 
{ 
for(j=1;j<=m;j++) 
{ 
if(j==1) 
{ 
solve[i][j]=solve[i-1][1]+data[i]; 
} 
 else if(j>i) 
break; 
else 
{ 
tem=100000000; 
 o=data[i]; 
for(k=i-1;k>=j-1;k--) 
{ 
t=solve[k][j-1]>o?solve[k][j-1]:o; 
if(t<tem) 
tem=t; 
o+=data[k]; 
} 
solve[i][j]=tem; 
} 
} 
} 
cout<<solve[n][m]<<endl; 
}