hdu 1244 Max Sum Plus Plus Plus DP

缘起

最大子段和之三连弹 ^_^ hdu 1244 Max Sum Plus 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
25
26
27
28
29
给定一个由n个正整数组成的整数序列
a1 a2 a3 ... an
求按先后次序在其中取m段长度分别为l1、l2、l3...lm的不交叠的连续整数的和的最大值。

Input
多样例
第一行是一个整数n(1 ≤ n ≤ 1000)，n = 0表示输入结束
第二行的第一个数是m(1 ≤ m ≤ 20)，
第二行接下来有m个整数l1，l2...lm。
第三行是n个整数a1, a2, a2 ... an.

Output
输出m段整数和的最大值。

Sample Input
3
2 1 1
1 2 3
4
2 1 2
1 2 3 5
0

Sample Output
5
10

限制
1s

和【1】相比，本题限定了子段的长度. 正因为固定了长度, 而【1】中的长度是不固定的. 所以变数更大. 所以本题其实比【1】更简单. 和【1】其实完全类似的，我们有

1
2
3
4
5
6
令dp[i][j]表示a[1,...,j]取i组(即l1,...,li片段)并且以a[j]为最后一组(第li组)的结束的最大和
则最终的答案就是 dp[m][l1+...+lm], dp[m][l1+...+lm+1],...,dp[m][n]的最大值
则dp方程是
dp[i][j] = max_{l1+..+l_{i-1}<=k<=j-li}{dp[i-1][k]}+a[j-li+1,...,j]的部分和
2<=i<=m, l1+...+li<=j<=n
而dp[1][j](l1<=j<=n)的初始值是取一组(长度为l1),以a[j]为结束的最大和. 那不就是部分和么?

而且本题因为n和m数据规模较小, 所以可以不滚动数组. 所以相当好写

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

int n,m,dp[25][1005],l[25],a[1005], sl[25], sa[1005], inf = ~0u>>1; // sl是l的部分和, sa是a的部分和

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	while(scanf("%d", &n),n)
	{
		scanf("%d", &m);
		for (int i = 1;i<=m; i++)
		{
			scanf("%d", l+i);
			sl[i] = sl[i-1]+l[i];
		}
		for (int i = 1; i<=n;i++)
		{
			scanf("%d", a+i);
			sa[i] = sa[i-1]+a[i];
		}
		for (int j = l[1]; j<=n; j++)
		{
			dp[1][j] = sa[j]-sa[j-l[1]];
		} // 初始化
		for (int i = 2,x; i<=m;i++)
		{
			x = -inf; // x就是dp方程中的 max_{l1+..+l_{i-1}<=k<=j-li}{dp[i-1][k]}
			for (int j = sl[i]; j<=n; j++)
			{
				x = max(x, dp[i-1][j-l[i]]); // 维护x
				dp[i][j] = x+sa[j]-sa[j-l[i]];
			}
		} // dp
		int ans = -inf;
		for (int i = sl[m]; i<=n; i++)
		{
			ans = max(ans, dp[m][i]);
		}
		printf("%d\n", ans);
	}
	return 0;
}

ac情况

Status Accepted
Time 15ms
Memory 1300kB
Length 887
Lang G++
Submitted 2019-09-12 19:01:44
Shared
RemoteRunId 30564464

参考

【1】https://yfsyfs.github.io/2019/09/12/hdu-1024-Max-Sum-Plus-Plus-m%E6%AE%B5%E4%B8%8D%E7%9B%B8%E4%BA%A4%E7%9A%84%E5%AD%90%E6%AE%B5%E5%92%8C%E7%9A%84%E6%9C%80%E5%A4%A7%E5%80%BC/