hdu 1024 Max Sum Plus Plus m段不相交的子段和的最大值

缘起

将原先做过的经典DP复习复习~ 喵~ hdu 1024 Max Sum Plus Plus

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
给你一个整数序列, 序列的长度<=100w, 每个数的值的绝对值<=32768 
定义片段和
sum(i, j) = ai + ... + aj (1 ≤ i ≤ j ≤ n)
现在给你一个正整数m, 你的任务是找到该序列的m个不相交的片段([1,2]和[3]是不交的.[1,2,3]和[3]
就是交的), 
使得这m个片段和的和达到最大.
输出这个最大和.

【输入】
多样例. 每个样例开始于m和n, 然后是n个整数构成的序列.

【输出】
最大和

【样例输入】
1 3 1 2 3
2 6 -1 4 -2 3 -2 3

【样例输出】
6
8

【限制】
1s

对于m=1, 就是【1】做的事情. 这里做的是一般的m的事情

经典DP问题, 和【1】是一样的. 令

1
2
3
4
5
6
7
8
9
dp[i][j]表示a[1,..,j]取i个片段并且最远的那个片段以a[j]为结束的最大值.
则dp方程是(按照是否将a[j]作为独立的一段来分情况)
dp[i][j] = max{dp[i][j-1], max_{i-1<=k<=j-1}{dp[i-1][k]}}+a[j], 1<i<=j<=n,i<=m
其中前者是不将a[j]单独作为第i个片段. 而后者是将a[j]单独作为第i个片段
dp的时候, i,j 都是正向. 
初始值 dp[1][j] 就是【1】做的事情. 
然后因为n可达100w, 所以必须要滚动数组进行优化. 即
dp[j] = max{dp[j-1], max{i-1<=k<=j-1}{dp[k]}}+a[j], 2<=i<=j<=n,i<=m i,j皆正向
其次, 为了防止被T, 缓存 max{i-1<=k<=j-1}{dp[k]} 是必须的.

看如下ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
//#include "stdafx.h"

#include <stdio.h>
#include <algorithm>
using namespace std;
//#define LOCAL
typedef long long LL;

const LL maxn = 1000005; // 一开始数组开小了, 被T掉了
LL dp[maxn],m,n,a[maxn],s[maxn];

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	while(~scanf("%lld%lld", &m,&n))
	{
		for (LL i = 1; i<=n; i++)
		{
			scanf("%lld", a+i);
			s[i] = s[i-1]+a[i];
		}
		dp[1] = a[1];
		for (LL j = 2; j<=n; j++)
		{
			dp[j] = max(dp[j-1], 0ll)+a[j];
		} // 初始化
		for (LL i = 2,t,x; i<=m; i++)
		{
			x = dp[i]; // 保存上一步的dp[i], 因为dp方程中的t就是用的[i-1]时的状态
			dp[i] = s[i]; // 本轮dp的起点. 前i个元素分成i个不交段,而且必须要以a[i]为结束,则只能是部分和
			t = s[i-1]; // max_{i-1<=k<=j-1}{dp[i-1][k]}, j=i+1起步,即max{dp[i-1][i-1],dp[i-1][i]}, 则dp[i-1][i-1]=s[i-1]作为t的起点即可,这是因为dp[i-1][i]不正是刚刚赋给的x吗?而第36行的max{t,x}就是max{dp[i-1][i-1],dp[i-1][i]},也就是说这里代码实现的比较技术性和精细
			for (LL j = i+1; j<=n; j++)
			{
				t = max(t, x); // t就是 max_{i-1<=k<=j-1}{dp[i-1][k]}
				x = dp[j]; // 缓存dp[j]变化之前的值,这是因为转移方程中是  max_{i-1<=k<=j-1}{dp[i-1][k]},即用到的是之前（i-1）的状态
				dp[j] = max(dp[j-1], t) + a[j];
			}
		}
		LL ans = 1ll<<63;
		for (int i = m; i<=n; i++) // j>=i
		{
			ans = max(ans, dp[i]);
		}
		printf("%lld\n", ans);
	}
	return 0;
}

ac情况

Status Accepted
Time 296ms
Memory 3584kB
Length 1086
Lang G++
Submitted 2019-09-12 18:04:44
Shared
RemoteRunId 30563984

参考

【1】https://yfsyfs.github.io/2019/07/20/%E7%BB%8F%E5%85%B8dpdp-%E6%B1%82%E6%9C%80%E5%A4%A7%E7%89%87%E6%AE%B5%E5%92%8C%E7%9A%84%E5%AD%90%E5%BA%8F%E5%88%97/