poj 2479 Maximum sum DP

缘起

日常浪费生命~ poj 2479 Maximum sum

本题其实就是【1】的m=2版本.

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
给你一个整数序列. 序列的个数n(2<=n<=50000). 每个整数的绝对值<=10000. 试求两个不交片段的最大和.

【输入】
多样例
第一行是样例数
每个样例由n开始. 第二行是n个整数.

【输出】
最大和

【样例输入】
1

10
1 -1 2 2 3 -3 4 -4 5 -5

【样例输出】
13

【限制】
1s

直接套 【1】中的代码水一道题目.~ QAQ

代码注释在【1】中.

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
50
51
52
53
//#include "stdafx.h"

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

const LL maxn = 1000005;
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
	int kase;
	scanf("%d", &kase);
	while(kase--)
	{
		scanf("%d", &n);
		m = 2;
		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[i] = s[i];  // 本轮dp的起点
			t = s[i-1]; 
			for (LL j = i+1; j<=n; j++)
			{
				t = max(t, x);
				x = dp[j];
				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 516ms
Memory 1296kB
Length 870
Lang C++
Submitted 2019-09-12 18:22:57
Shared
RemoteRunId 20855587

参考

【1】https://yfsyfs.github.io/2019/09/12/hdu-1024-Max-Sum-Plus-Plus-m段不相交的子段和的最大值/