杭电60题--part 1 HDU1003 Max Sum（DP 动态规划）

最近想学DP，锻炼思维，记录一下自己踩到的坑,来写一波详细的结题报告，持续更新。

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

Problem Description

Given a sequence a[1],a[2],a[3]......a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.

Input

The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000).

Output

For each test case, you should output two lines. The first line is "Case #:", # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.

Sample Input

2 5 6 -1 5 4 -7 7 0 6 -1 1 -6 7 -5

Sample Output

Case 1: 14 1 4 Case 2: 7 1 6

Author

Ignatius.L

Recommend

We have carefully selected several similar problems for you: 1069 2084 1058 1421 1024

这一个题是一个基本题型，先分析数据这点很重要，刚刚踩坑，这里每个ai大于-1000，小于1000，那么min为-1e3*1e5，也就是说求和后最小值最大值为1e8量级，那么比较时最大最小值一定设置比这个量级大或在这个量级最大，而我没考虑到如果全为负数时的情况。

开始说题目，这个题目找最大子串，对于任意一个元素，它有两种可能性，做上个子串的最后一个字符，作以自己开头的子串的第一个字符，我们这里不考虑当前字符后续字符，因为DP子问题无后效性，那么两种状态到了，我们要找出两种状态分支的条件，如果一个元素跟着前面的大哥混没前途，那就不跟他混了，自立山头，不前面序列的和都小于0，不如自己做开头。即可写出状态转移方程。 $dp(x)=left{ egin{aligned} dp[i-1]+a[i] &if(dp[i-1]>0)\ a[i]&if(dp[i-1]<0) end{aligned} ight.$ ,这里问什么没写等于0呢，因为题目的要求是找最靠前的左端点，所以这等于号要放到上面，但是我们怎么存储端点呢？一样的状态转移，我跟前面的老大哥们混，我的头头肯定是前面的老大哥，所以那我的老大哥也是这个子序列的第一个，如果这个小团伙没落了，我自立山头，那么后来的人的大哥肯定会是我，所以就有了状态转移方程，再开一维，也可以再开一个数组，我不太建议跑好几遍循环的方法，能简化就简化。

if(dp[i-1][1]<0||i==1) //i==1细节操作，自己想一下
{
    dp[i][0]=i;
    dp[i][1]=a[i];
}
else
{
    dp[i][0]=dp[i-1][0];
    dp[i][1]=dp[i-1][1]+a[i];
}

应该没什么要注意了，还有就是初始化，这是多组输入。