一道动态规划例题-杭电1024

问题描述：

给定一个长度为n的整数的数组，现在让你将整个数组分成m段，并且这m段互不相交，在所有分段方式中能够得到的这m段子数组的最大的和是多少？

解析：

本题是一道适合用动态规划方式解决的问题，首先定义两个状态：f[i][j]，g[i][j].

f[i][j]是将前i个元素分成j段并且包含第i元素的最大和；

g[i][j]是将前i个元素分成j段并且不一定包含第i元素的最大和；

则状态转移方程为：

f[i][j]=max(f[i-1][j]+data[i],g[i-1][j-1]+data[i]),即第i元素data[i]可能和前面的元素一起组成第j段，也可能是自己单独是第j段；

g[i][j]=max(f[i][j],g[i-1][j]),即g[i][j]为包含第i元素的j段和与不包含第i元素j段和的最大值；

g[n][m]即为最终整个数组分成m段，并且这m段互不相交，在所有分段方式中能够得到的这m段子数组的最大的和；

下面程序中可以将两个二维数组f,g压缩为一维进行计算，程序如下：

<SPAN style="FONT-FAMILY: Times New Roman">#include<iostream>
using namespace std;
int max_sum(const int *data,int n,int m);
int max(int a,int b);
int main()
{
	int n,m,i;
	cin>>n>>m;
	int *data=new int[n+1];
	for(i=1;i<=n;i++)
		cin>>data[i];
	int maxsum=max_sum(data,n,m);
	cout<<maxsum<<endl;
	delete []data;
	return 0;
}
int max_sum(const int *data,int n,int m)
{
	int i,j;
	int *f=new int[m+1];
	int *g=new int[m+1];
	for(i=0;i<=m;i++)
	{
		f[i]=0;
		g[i]=0;
	}
	for(i=1;i<=n;i++)
	{
		for(j=m;j>=1;j--)
		{
			f[j]=max(f[j]+data[i],g[j-1]+data[i]);
			g[j]=max(f[j],g[j]);
		}
	}
	int result=g[m];
	delete []f;
	delete []g;
	return result;
}
int max(int a,int b)
{
	if(a>b)
		return a;
	else
		return b;</SPAN>
}

补充：软件开发 , C++ ,