WEEK12 作業 C - 必做題3

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 處理到 EOF

Output

輸出最大和。

Sample Input

1 3 1 2 3
2 6 -1 4 -2 3 -2 3
           

Sample Output

6
8
           

Hint

資料量很大，需要scanf讀入和dp處理。

題解

區間動态規劃問題。

dp[i][j]：在前j個元素中選出不重合的i段的總和是多少（且第j個元素a[j]必須包含在其中）。

狀态轉移方程：dp[i][j]=max{dp[i][j-1]+a[j],dp[i-1][k]+a[j]} i-1<=k<=j-1将a[j]放在上一段末尾或将a[j]放在新的一段。

但是由于資料量很大，不可能同時存儲這麼多數，且我們注意到，dp[i-1][k]隻在dp[i][j]的更新中用到，是以可以記錄下在a[1]-a[j]中選i-1（上一次循環）段的最大和結果數，在時間和空間上同時優化掉一維。令mx[j]為上一個狀态的dp最大值，即在a[1]-a[j]中選i-1段的最大和。

優化後的狀态轉移方程：dp[j]=max(dp[j-1]+a[j],mx[j-1]+a[j])。

最後結果就是選i段的最大值ans。

代碼

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int a[1000100],dp[1000100],mx[1000100];
int main(int argc, char** argv) {
	int m,n;
	while(scanf("%d%d",&m,&n)!=EOF){
		memset(dp,0,sizeof(dp));
		memset(mx,0,sizeof(mx));
		for(int i=1;i<=n;i++){scanf("%d",&a[i]);}
		int ans;
		for(int i=1;i<=m;i++){
			ans=-100000000;
			for(int j=i;j<=n;j++){
				dp[j]=max(dp[j-1]+a[j],mx[j-1]+a[j]);
				mx[j-1]=ans;
				ans=max(ans,dp[j]);
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}