hdu 1024 Max Sum Plus Plus

Problem

acm.hdu.edu.cn/showproblem.php?pid=1024

题意

给一个长为 n 的序列，有从中挑 m 个相互不重合的子序列求总和，让总和最大。

分析

（没能看懂百度的前几份题解…好像都跟 kuangbin 的写法差不多：www.cnblogs.com/kuangbin/archive/2011/08/04/2127085.html）

下面是同学教的思路：

dp[ i ][ j ][ 0/1 ]：从前 i 个数中挑 j 个子序列的最大和，第 3 维分别用 0 和 1 表示第 i 个数是否包括在第 j 个子序列内（最后一个数只能在最后一个序列内）

转移方程：dp[ i ][ j ][ 0 ] = max { dp[ i-1 ][ j ][ 0 ] , dp[ i-1 ][ j ][ 1 ] }

dp[ i ][ j ][ 1 ] = max { dp[ i-1 ][ j ][ 1 ] + s[ i ] , dp[ i-1 ][ j-1 ][ 1 ] + s[ i ] , dp[ i-1 ][ j-1 ][ 0 ] + s[ i ] }（s[ i ]附在最后一个序列尾，或自成一个新序列）

因为不知道 m 多大，所以第一维用滚动数组

Source code

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1000000;
const long long INF = 1234567891011LL;

int s[N+1];
long long dp[2][N+1][2] = {0};

int main()
{
	int m, n;
	while(~scanf("%d%d", &m, &n))
	{
		for(int i=1; i<=n; ++i)
			scanf("%d", s+i);
		for(int i=0; i<2; ++i)
			for(int j=1; j<=m; ++j)
				dp[i][j][0] = dp[i][j][1] = -INF;
		for(int i=1; i<=n; ++i)
			for(int j=1; j<=m; ++j)
			{
				dp[i&1][j][0] = max(dp[i&1^1][j][0], dp[i&1^1][j][1]);
				dp[i&1][j][1] = s[i] + max(dp[i&1^1][j][1],
					max(dp[i&1^1][j-1][0], dp[i&1^1][j-1][1]));
			}
		printf("%I64d\n", max(dp[n&1][m][0], dp[n&1][m][1]));
	}
	return 0;
}

这份代码有点神奇，之前初始化的第 2 层循环是从 1 到 N，一直 MLE；换成从 1 到 m 后就没有爆内存了。dp 数组应该是定义之后就分配了固定大小了吧？不知道为什么有影响。

另外，从转移方程可以看出，第 1 维应该可以省去，只要里层循环改成倒序就行了。于是改写一发。

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1000000;
const long long BIG = 1234567891011LL;

int s[N+1];
long long han[N+1] = {0}; // 原dp[][][1]
long long bu[N+1] = {0}; // 原dp[][][0]

int main()
{
	int m, n;
	while(~scanf("%d%d", &m, &n))
	{
		for(int i=1; i<=n; ++i)
			scanf("%d", s+i);
		for(int j=1; j<=m; ++j)
			han[j] = bu[j] = -BIG;
		for(int i=1; i<=n; ++i)
			for(int j=m; j; --j)
			{
				bu[j] = max(bu[j], han[j]);
				han[j] = s[i] + max(han[j],
					max(han[j-1], bu[j-1]));
			}
		printf("%I64d\n", max(han[m], bu[m]));
	}
	return 0;
}

最后附上 Maple 的还没看懂的代码