首页 > HDOJ解题报告 > HDU 1003 Max Sum[DP]

HDU 1003 Max Sum[DP]

水题,很久以前做过的,现在做起来竟然WA了不少次,唉,好久没接触DP了。
这个题就是最大子段和了,不过要求出子段的起始位置和结束位置。答案会有多种,比如某一个连续子段和为0的,要不要算进去,实际上测试的时候算进去和不算进去都是AC的。
状态转移方程:sum[i + 1] = sum[i] > 0 ? sum[i] + num[i + 1] : num[i + 1](这里写成sum[i] >= 0不影响正确性)
下面是AC代码,比较混乱。
HDU 1003 Max Sum[DP] 题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1003

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
54
55
56
57
58
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define MAX_NUM 100010
int num[MAX_NUM];
 
void GetMaxPos(int m, int& left, int& right, int& max)
{
	int i = 0, tmp = 0;
	int l, r, tl;
	tl = l = r = 0;
	max = -1000;
	for (i = 0; i < m; ++i)
	{
		tmp += num[i];
		if (tmp > max)
		{
			max = tmp;
			r = i;
			l = tl;
		}
		if (tmp < 0)
		{
			tmp = 0;
			tl = i + 1;
		}
	}
	left = ++l;
	right = ++r;
}
 
int main(int argc, char **argv)
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
 
	int n, m, i, j;
	scanf ("%d", &n);
	for (j = 1; j <= n; ++j)
	{
		scanf ("%d", &m);
		for (i = 0; i < m; ++i)
		{
			scanf ("%d", &num[i]);
		}
		int left, right, max;
		left = right = 0;
		max = -2000;
		GetMaxPos(m, left, right, max);
		printf ("Case %d:\n", j);
		printf ("%d %d %d\n", max, left, right);
		if (j != n)
			putchar('\n');
	}
 
	return 0;
}

觉得文章还不错?点击此处对作者进行打赏!


本文地址: 程序人生 >> HDU 1003 Max Sum[DP]
作者:代码疯子(Wins0n) 本站内容如无声明均属原创,转载请保留作者信息与原文链接,谢谢!


更多



  1. 2012年5月17日19:54 | #1

    咦,为什么不去搞呢,ACM挺好玩的啊,博主 [em022] 解题报告比较少

    [回复]