【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)

思路：

令f[i][j]是前i个扫j次的最大值(一定会扫a[i])，f[i][j]=max{f[i-1][j]+a[i],f[k][j-1]+a[i]} j-1<=k<=i-1（分为i与前面一起扫和i单独扫两种情况）。
发现可以优化掉数组第二维j。
即遍历j=1~m，f[i]=max{f[i-1]+a[i],f[k]+a[i]}。
然后f[k]可以取扫j-1次的f[j-1]~f[i-1]最大值： 令maxf[i]为j-1次的f[j-1]~f[i]最大值，f[i]=max{f[i-1]+a[i],maxf[i-1]+a[i]}。
注意maxf[i]的更新，这一轮j的maxf要在下一轮j+1使用。
最后答案是f[m]~f[n]中的最大值， 不能从f[1]~f[n]中取最大值，因为前k个是只扫了k轮(k<m)，不是正确答案。

总结：

一道动态规划题目，想公式很费劲，优化也不好想。多做一些dp题应该会有改善。

代码：

#include <iostream>
#include <stdio.h>
using namespace std;

//令f[i][j]是前i个扫j次的最大值(一定会扫a[i])
//f[i][j]=max{f[i-1][j]+a[i],f[k][j-1]+a[i]} j-1<=k<=i-1
//发现可以优化掉j
//即遍历j=1~m
//f[i]=max{f[i-1]+a[i],f[k]+a[i]}
//然后f[k]可以取扫j-1次的f[j-1]~f[i-1]最大值
//令maxf[i]为j-1次的f[j-1]~f[i]最大值
//f[i]=max{f[i-1]+a[i],maxf[i-1]+a[i]}
int m,n;
int a[1000010];
int f[1000010];
int maxf[1000010];
int ans;
int main()
{
	while(scanf("%d%d",&m,&n)!=EOF)
	{
		for(int i=1; i<=n; i++)
			scanf("%d",&a[i]);
		for(int i=0;i<=n;i++)
			f[i]=0,maxf[i]=0;
		ans=-1e9;
		for(int j=1; j<=m; j++)
		{
			for(int i=j; i<=n; i++)
			{
				int a1=f[i-1]+a[i],a2=maxf[i-1]+a[i];
				f[i]=max(a1,a2);
				//更新maxf[i-1]
				if(i==j||i==j+1)	//新一轮j,要重新来,下一轮j+1要用到这一轮的maxf[j]~maxf[n-1] 
					maxf[i-1]=f[i-1];
				else	maxf[i-1]=max(maxf[i-2],f[i-1]); 
			}
		}
		for(int i=m;i<=n;i++)	//注意从m开始,不然前k个为只扫k轮(k<m),可能会错 
			if(ans<f[i])
				ans=f[i];
		printf("%d\n",ans);
	}
}