HDU 1024 Max Sum Plus Plus （动态规划、最大m子段和）

时间：2022-05-17 20:00:55

Max Sum Plus Plus

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 44371    Accepted Submission(s): 16084

Problem Description

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. ^_^



Input

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

Output the maximal summation described above in one line.



Sample Input

  -  -  -

Sample Output





题目大意


从一序列中取出若干段，这些段之间不能交叉，使得和最大并输出。、


题目分析


动态规划 首先我们可以列出最基本的状态转移方程：


　　　　dp[i][j] = max( dp[i][j-1] + a[j] , dp[i-1][k] + a[j ])    i-1<=k<=j-1


　　　　这个方程的含义是：


　　　　　　　　dp[i][j] 是将前 j 个数分成 i 份，且第 i 份包含第 j 个数 的情况下的最大值


　　　　　　　　那么对于第 j 个数来说，就有两个选择：


　　　　　　　　　　　　　　作为第 i 份的一部分 ：也就是将前 j-1 个数分成 i 份 且第 j-1 个数属于第 i 份 即 dp[i][j-1]


　　　　　　　　　　　　　　或者单独出来成为第 i 份：也就是将前 j-1 个数分成 i-1 份 且第 j-1 个数不一定属于第 i-1 份  即 dp[i-1][k] i-1<=k<=j-1


但是这个方程不仅时间复杂度高，空间复杂度也高的可怕 这是不行的


所以我们要将其优化：


首先我们发现 dp[i][j] 只需要比较 dp[i][j-1] 与 dp[i-1][k] 的最大值即可 而这个 dp[i-1][k] 的最大值是可以记录下来的 不需要遍历 这就砍去了一层循环


　　　　所以我们只需要定义一个 pre[n] 数组 用 pre[j] 来存储第 j-1 个数被分成 i-1 份时的最大值即可


　　　　于此同时 在计算 dp[i][j] 时，我们可以计算出 dp[i][k] i<=k<=j 的值 而这个值是在之后我们要计算 dp[i+1][j+1] 时 要使用的 pre[j]


现在状态转移方程变成了：
　　　　dp[i][j] = max( dp[i][j-1] + a[j] , pre[j-1] + a[j ])


现在我们发现 由于pre[j] 的存在 似乎已经不需要 dp[i][j] 这个庞大的二维数组了 只需要开一个 dp[n] 的数组 用dp[j]来存储dp[i][j]即可，因为当前的转移方程根本就没有用到 i 这一维！


这样的话 转移方程又变成了：
　　　　dp[j] = max( dp[j-1] + a[j] , pre[j-1] + a[j ])


不过 i 的这一层循环还是得循环的 这个砍不掉的...




#include<bits/stdc++.h>

using namespace std;

int n,m,dp[],a[],pre[],i,j,temp;

int main()

{

    while(scanf("%d %d",&m,&n)!=EOF)

    {

        memset(dp,,sizeof(dp));

        memset(a,,sizeof(a));

        memset(pre,,sizeof(pre));

        for(i=;i<=n;i++)

        {

            scanf("%d",&a[i]);

         }

        for(i=;i<=m;i++)

        {

            temp=-0x7ffffff;

            for(j=i;j<=n;j++)

            {

                dp[j]=max(dp[j-],pre[j-])+a[j];

                pre[j-]=temp;

                temp=max(temp,dp[j]);

            }

        }

        cout<<temp<<endl;

    }

}


相关文章