HDU - 1024 Max Sum Plus Plus 动归 m子段和最大值

用户2965768

发布于 2019-08-01 10:20:04

3820

发布于 2019-08-01 10:20:04

文章被收录于专栏：wym

题意：给m n n个数，求m个连续段的和最大值

状态转移：以 j 结尾的的 i 个子段和的最值，那么最值一定在这个过程中。

由于以j结尾，对于每个a[j]必须要选，可以让它附在前一段后面也可以让它自成一段。

dp[i][j] = max(dp[i][j-1] + a[j], max(dp[i-1][k]) + a[j] ) k: i-1~j-1

其中 max(dp[i-1][k])表示前 j - 1项选取 i-1段以 k 结尾的最大值。

实现这个状态转移需要三层循环，限时 1 s，需要优化

我们发现最内层循环 for(int k=i-1;k<=j-1;k++) dp[i][j] = max(dp[i][j-1] + a[j], dp[i-1][k] + a[j] )

最终dp[i-1][k]求出来的就是 dp[i-1][ j ] 过程中的某一个值，以 j 结尾比以 k 结尾范围要大。

用一个数组记录即可。

//HDU - 1024 
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 1e6+15;
const int inf = 0x7fffffff;
int dp[maxn],a[maxn],maxc[maxn];
int m,n,ans;
int main()
{
	while(~scanf("%d %d",&m,&n)){
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
		}
		memset(dp,0,sizeof(dp));
        memset(maxc,0,sizeof(maxc));
		for(int i=1;i<=m;i++){
			ans = -inf;
			for(int j=i;j<=n;j++){
				dp[j] = max(dp[j-1]+a[j], maxc[j-1]+a[j]);
				maxc[j-1] = ans;
				ans = max(dp[j],ans);
			}
		}	
		printf("%d\n",ans);
	}
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019年07月20日，如有侵权请联系 cloudcommunity@tencent.com 删除