首页 > ACM题库 > HDU-杭电 > HDU 1244 Max Sum Plus Plus Plus-动态规划-[解题报告] C++
2013
12-04

HDU 1244 Max Sum Plus Plus Plus-动态规划-[解题报告] C++

Max Sum Plus Plus Plus

问题描述 :

给定一个由n个正整数组成的整数序列

a1 a2 a3 … an

求按先后次序在其中取m段长度分别为l1、l2、l3…lm的不交叠的连续整数的和的最大值。

输入:

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

输出:

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

样例输入:

3
2 1 1
1 2 3
4
2 1 2
1 2 3 5
0

样例输出:

5
10

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1244

题目大意:给定一个由n个正整数组成的整数序列a1 a2 a3 … an,求按先后次序在其中取m段长度分别为l1、l2、l3…lm的不交叠的连续整数的和的最大值。

解题思路:状态转移方程:dp[i][j] = max(dp[i][j-1],dp[i-1][j-len[i]] + sum[j] – sum[j-len[i]]) (dp[i][j]表示当前选择第i个长度为len[i]的区间算,位置j之前的最大和。dp[i][j-1]和dp[i-1][j-len[i]必须是已经算过并可行的)

    因为要按顺序选择m段长度为len[i]的连续整数相加,且每段区域不重叠,很明显没有后效性,所以断定是动规题。由于前一次选择的区间影响后一次选择,可以想到状态转移方程要体现选择了第几段区间。再想下肯定要选一维存放位置,不然没办法保证不重叠。想了这么多,状态转移方程也就出来了。至于为什么要从dp[i][j-1]转移,可以这样理解,dp[i][j-1]表示选择i段不重叠区间并且算得最远距离到j-1的和的最大值,虽然后面不再选择区间,也需要更新位置比j-1远的值,比如8
7 9,我要选择了一段长度为1的区间,dp[1][1] = 8肯定没错,dp[1][2]是7吗?明显不是,是8.

测试数据:

7

1 1

7 8 9 2 3 5 6


7
2 1 2

7 8 9 2 3 5 6


7
3 1 2 1

7 8 9 2 3 5 6


7
4 1 2 1 3

7 8 9 2 3 5 6


代码:

#include <stdio.h>
#include <string.h>
#define MAX 1010
#define INF -1
#define max(a,b) (a) > (b) ? (a) : (b)


int n,m,len[30],arr[MAX];
int sum[MAX],dp[30][MAX];


int Solve() {

	int i,j,k,ans;
	for (i = 1; i <= m; ++i)
		for (j = 0; j <= n; ++j)
			dp[i][j] = INF;

	
	for (i = 1; i <= m; ++i) 
		for (j = len[i]; j <= n; ++j)
			if (dp[i-1][j-len[i]] != INF) {

				int tp = dp[i-1][j-len[i]];
				tp += sum[j] - sum[j-len[i]];
				dp[i][j] = max(tp,dp[i][j]);
				if (dp[i][j-1] != INF)
					dp[i][j] = max(dp[i][j],dp[i][j-1]);
			}


	ans = INF;
	for (i = 1; i <= n; ++i)
		if (dp[m][i] != INF) ans = max(ans,dp[m][i]);
	return ans == INF ? 0 : ans;
}


int main()
{
	int i,j,k;


	while (scanf("%d",&n) ,n) {

		scanf("%d",&m);
		for (i = 1; i <= m; ++i)
			scanf("%d",&len[i]);
		memset(sum,0,sizeof(sum));
		for (i = 1; i <= n; ++i)
			scanf("%d",&arr[i]),sum[i] = sum[i-1] + arr[i];	

		
		printf("%d\n",Solve());
	}
}


本文ZeroClock原创,但可以转载,因为我们是兄弟。


  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。