程序设计思维与实践 Week12 作业 C 必做题 - 3

题目描述：

东东每个学期都会去寝室接受扫楼的任务，并清点每个寝室的人数。
每个寝室里面有ai个人(1<=i<=n)。从第i到第j个宿舍一共有sum(i,j)=a[i]+...+a[j]个人
这让宿管阿姨非常开心，并且让东东扫楼m次，每一次数第i到第j个宿舍sum(i,j)
问题是要找到sum(i1, j1) + ... + sum(im,jm)的最大值。且ix <= iy <=jx和ix <= jy <=jx的情况是不被允许的。也就是说m段都不能相交。
注：1 ≤ i ≤ n ≤ 1e6 , -32768 ≤ ai ≤ 32767 人数可以为负数。。。。(1<=n<=1000000)

input：

输入m，输入n。后面跟着输入n个ai

output：

输出最大和

思路：

最大m区间和问题。f[i][j]表示取第j个数，并且前j个数共分成i个区间的最大和，状态转移方程为：f[i][j]=max(f[i][j-1]+a[j], f[i-1][k]+a[j])   k从(i-1)到(j-1)。其中，f[i][j-1]+a[j]表示在取第j-1个数的基础上，加上第j个数，所以并没有增加新的区间。f[i-1][k]+a[j]表示已经有了i-1个区间，第j个数的加入产生了一个新的区间，所以根据这个思路，k应该从i-1到j-1取值。

根据f数组的定义，可以存在i==j的情况，因此会同时出现f[i][j-1]即：f[i][i-1]的情况，i-1个数却分出了i个区间，这显然不成立。因此将f[i][i-1]设置为极小值即可。

与此同时，观察到n和m会非常大，用二维数组会超空间。此时考虑空间的优化：第一层循环从1到m遍历i，在状态转移方程中，f[i][j-1]+a[j]并没有用到第i-1层的内容，而f[i-1][k]+a[j]虽然用到了，但是可以再开一个变量，在i-1层更新的过程中，将其记录下来。因此，f数组第一维可以去掉。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int minn=-(1e9+1e8);
int n,m,f[1000010],a[1000010],ff[1000010];
int main()
{
    while(scanf("%d",&m)!=EOF)
	{
		memset(ff,0,sizeof(ff));
		memset(f,0,sizeof(f));
		int ans=minn;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
		for(int i=1;i<=m;i++)
		{
			int smal=minn;
			for(int j=i;j<=n;j++)
			{
				f[i-1]=minn;
				f[j]=max(f[j-1]+a[j],ff[j-1]+a[j]);
				ff[j-1]=smal;
				smal=max(f[j],smal);
				if(i==m)
				ans=max(f[j],ans);
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}