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

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

Max Sum Plus Plus

问题描述 :

Now I think you have got an AC in Ignatius.L’s "Max Sum" problem. To be a brave ACMer, we always challenge ourselves to more difficult problems. Now you are faced with a more difficult problem.

Given a consecutive number sequence S1, S2, S3, S4 … Sx, … Sn (1 ≤ x ≤ n ≤ 1,000,000, -32768 ≤ Sx ≤ 32767). We define a function sum(i, j) = Si + … + Sj (1 ≤ i ≤ j ≤ n).

Now given an integer m (m > 0), your task is to find m pairs of i and j which make sum(i1, j1) + sum(i2, j2) + sum(i3, j3) + … + sum(im, jm) maximal (ix ≤ iy ≤ jx or ix ≤ jy ≤ jx is not allowed).

But I`m lazy, I don’t want to write a special-judge module, so you don’t have to output m pairs of i and j, just output the maximal summation of sum(ix, jx)(1 ≤ x ≤ m) instead. ^_^

输入:

Each test case will begin with two integers m and n, followed by n integers S1, S2, S3 … Sn.
Process to the end of file.

输出:

Output the maximal summation described above in one line.

样例输入:

1 3 1 2 3
2 6 -1 4 -2 3 -2 3

样例输出:

6
8

Hint
Huge input, scanf and dynamic programming is recommended.

HDU-1024 http://acm.hdu.edu.cn/showproblem.php?pid=1024

  题意是给定n个数,和m个段。求在这n个数中求出m个子段,使得这些子段的和最大。由于这题给的n很大,需要用dp来解。

  考虑把每一个段作为状态转移中的状态,那么对于每一个既定的状态,考虑其可能决策的方向:

  当前这个状态是dp[i][j],i 表示当前的段,j表示前j个数组成了当前的这i个段,并且保证dp[i][j]是当前决策的最优解。

  1. 状态dp[i][j]可以从dp[i][j-1]转移过来,表示第j个数字正好可以和 i 个段的前j-1个数字相加的和是当前所在状态中最大的
  2. 状态dp[i][j]可以从dp[i-1][j-1]转移过来,表示第 j 个数字正好可以成为第 i 个段,并且使得和i-1个段相加的和是当前所有状态中最大的

  在这题中如果使用O(n^2)的空间复杂度,可能会空间太大,所以考虑到每次的状态转移总是和其前一个状态有关,所以可以使用滚动数组存储。在使用滚懂数组存储的时候,需要考虑:其中第一个决策可以保证前一个状态dp[i][j-1]每次都是被更新的,而对于第二个决策,需要保证dp[i-1][j-1]在每一次j改变的时候都要更新,使得dp[i-1][j-1]是最大的。

1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 #define M 1000005
 5 #define MAX(x, y) ((x) > (y) ? (x) : (y))
 6 
 7 int dp[2][M];
 8 int num[M];
 9 
10 int main(void)
11 {
12     int t, i, j;
13     int n, m;
14     int max;
15 
16     while(~scanf("%d%d", &m, &n))
17     {
18     for(i = 1; i <= n; i++)
19     {
20         dp[0][i] = 0;
21         dp[1][i] = 0;
22         scanf("%d", num + i);
23     }
24     for(i = 1, t = 1; i <= m; i++, t = !t)
25     {
26         dp[t][i] = dp[!t][i-1] + num[i];
27         dp[!t][i] = MAX(dp[!t][i], dp[!t][i-1]);
28         for(j = i+1; j <= n - m + i; j++)
29         {
30         dp[t][j] = MAX(dp[!t][j-1], dp[t][j-1]) + num[j];
31         dp[!t][j] = MAX(dp[!t][j], dp[!t][j-1]);
32         }
33     }
34     max = -(1 << 30);
35     for(i = m; i <= n; i++)
36         max = MAX(max, dp[m&1][i]);
37     printf("%d\n", max);
38     }
39     return 0;
40 }

 


  1. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept