040320164_2.cpp

最小M段和问题！ 这个是用动态规划实现的！ 自顶向下的备忘录方法实现的！

#include<iostream.h>
#include<fstream.h>
long a[2000][2000],M[2000][2000];
int n;
void main()
{
    int m;
	long f(int,int);
	ifstream infile("input.txt");
	ofstream outfile("output.txt");
    infile>>n;
	infile>>m;
	for( int i=1;i<=n;++i) 	infile>>a[i][i];
	for(i=1;i<n;i++)
		for( int j=i+1;j<=n;j++)
		 	a[i][j]=a[i][j-1]+a[j][j];			
   outfile<<f(1,m);
}
long f(int b,int k)
{
	if(k==1) return a[b][n];
	long Min=1000000000,S;
	for(int i=b;i<=n-k+1;i++)
	{
		if(M[i+1][k-1]==0)
			M[i+1][k-1]=f(i+1,k-1);
		S=M[i+1][k-1];
		if(S<a[b][i])
			S=a[b][i];
		if(Min>S) Min=S;
	}
	return Min;
}
解题报告
	
一、	    问题：给定n个整数组成的序列，现在要求将序列分割为m段，每段子序列中的数在原序列中连续排列。如何分割才能使这m段子序列的和的最大值达到最小？       把n=5 ，m＝3，A={1,2,3,4,5} 解为6。
二、	   设计： 设b(ｉ，j)表示把数组A的第ｉ个开始到N划分成j段，且第一个字段含A[ｉ](1<=ｉ<=n,1<=j<=m)。则所求的值显然为b(ｉ，j)。计算b(ｉ，j)的递归式为：
       b(ｉ，j)＝min ( max ( a (ｉ,k),  b(k+1，j-1) ))  (ｉ<=k<=n-m+ｉ) (1<=ｉ<=n,1<=j<=m) 其中a (ｉ,k)表示数组A从到k的和，max ( a (ｉ,k),  b(k+1，j-1)) (ｉ<=k<=n-m+ｉ)表示把数组A的第ｉ个开始到N划分成j段后，这m段子序列的和的最大值的集合，初始值b(ｉ，1)= a (ｉ,n) (m<=ｉ<=n)。
       根据上述计算b(ｉ，j)的递归式，可把 b(ｉ，j) 改为函数Trace (ｉ，j ), 求Trace(1，m),算法如下：
          int Trace(int Start,int Num)
{
	          if(Num==1) return a[Start][n];
	          int Min=Maxinteger,temp;
	         for(int i=Start;i<=n-Num+1;i++) 
	         {
		        temp=(a[Start][i]>=Trace(i+1,Num-1)?a[Start][i]:Trace(i+1,Num-1));
		        if(Min>temp) Min=temp;
	         }
	         return Min;
}	
三、	改进：用MaxValue [i][Num-1]保存Trace(i+1,Num-1)已计算过的值，先给赋初值MaxValue [i][Num-1] =Maxinteger，表示Trace(i+1,Num-1)未计算。算法如下：
       int Trace(int Start,int Num)
{
	    if(Num==1) return  a[Start][n];
	    int Min=Maxinteger, temp;
	    for(int i=Start;i<=n-Num+1;i++)
	    {
		  if(MaxValue[i][Num-1]==Maxinteger) MaxValue[i][Num-1]=Trace(i+1,Num-1);
		  temp= a[Start][i])>MaxValue[i][Num-1]? a[Start][i]):MaxValue[i][Num-1];
		  if(Min> temp) Min= temp;
	    }
	    return Min;
}
四、	用动态规划递归式计算b(ｉ，j)，由b(ｉ，j)＝min ( max ( a (ｉ,k),  b(k+1，j-1) ))  (ｉ<=k<=n-m+ｉ) (1<=ｉ<=n,1<=j<=m) 可以看出，计算b(ｉ，j)时只用到数组b的第j-1列的值。因而算法值要存储数组b的当前列，不必保存整个数组，故可用b的一维数组就可以了，算法如下：

int Trace ()
{ 
 for(i=1;i<=n-m+1;i++) b[i]=a[1][i];
	for(i=2;i<=m;i++)
    {	
		b[i]=b[i-1]>a[i][i]?b[i-1]:a[i][i];
		for(int j=n-m+i;j>=i+1;j--)
		{
			b[j]=b[j-1]>a[j][j]?b[j-1]:a[j][j];			
			for(int k=j-2;k>=i-1;k--)
			{
				int temp=b[k]>a[k+1][j]?b[k]:a[k+1][j];
				if(temp<b[j]) b[j]=temp;
			}
		}	
	}
   return b[n];
}
五、效率：T(n)=O(m*n^2),S(n)=O(n^2);