hdu1024 Max Sum Plus Plus 滚动dp

Max Sum Plus Plus

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

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 S₁, S₂, S₃, S₄ ... S_x, ... S_n (1 ≤ x ≤ n ≤ 1,000,000, -32768 ≤ S_x ≤ 32767). We define a function sum(i, j) = S_i + ... + S_j (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(i₁, j₁) + sum(i₂, j₂) + sum(i₃, j₃) + ... + sum(i_m, j_m) maximal (i_x ≤ i_y ≤ j_x or i_x ≤ j_y ≤ j_x 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(i_x, j_x)(1 ≤ x ≤ m) instead. ^_^

Input

Each test case will begin with two integers m and n, followed by n integers S₁, S₂, S₃ ... S_n.
Process to the end of file.

Output

Output the maximal summation described above in one line.

Sample Input

1 3 1 2 3

2 6 -1 4 -2 3 -2 3

Sample Output

题意：输入有多个样例，每个样例输入只有一行m,n，接下来在同一行给定n个数。输出就是把这n个数分成m个不相交的子段，输出使这m个子段的和的最大值。

题解：用动态规划，dp[i][j]表示把数组a的前j个数分成i个子段的和。对于于每一个数a[j]要考虑两个状态：即a[j]要么加入与它相邻的前一个子段，要么自己单独成为一个子段，

据此列出动态转移方程为dp[i][j]=max(dp[i][j-1]+a[j],dp[i-1][x]+a[j]),i-1<=x<=j-1,dp[i-1][x]表示把数组a的前x个数分成i-1个子段的和的最大值。

因为n给的范围比较大，直接三层for循环显然会超时。

TLE的代码

#include<iostream>
#include<math.h>
#define ll long long
using namespace std;
ll dp[200][200000],a[2000000];//dp[i][j]表示将数组a中前j个数分成 i组的最大和
int main()
{
    ll n,m;
    while(~scanf("%lld%lld",&m,&n))
    {
        for(int i=1;i<=n;i++)
            cin>>a[i];
        for(int i=1;i<=m;i++)
        {
            for(int j=i;j<=n;j++)
            {
                ll temp=-99999999999999;
                for(int x=i-1;x<=j-1;x++)
                {
                    temp=dp[i-1][x]>temp?dp[i-1][x]:temp;
                }
                dp[i][j]=dp[i][j-1]+a[j]>temp+a[j]?dp[i][j-1]+a[j]:temp+a[j];
            }
            
        }
        cout<<dp[m][n]<<endl;
    }
    return 0;
}

滚动DP优化

对动态转移方程：dp[i][j]=max(dp[i][j-1]+a[j],dp[i-1][x]+a[j]),i-1<=x<=j-1,dp[i-1][x]表示把数组a的前x个数分成i-1个子段的和的最大值。通过转移方程我们可以看出，对于求下一个dp[i][j]我们

只用到它的前两个状态dp[i][j-1]和dp[i-1][x]，dp[i][j-1]在上一层循环中已经求出来了，因此我们只要再开一个滚动数组mx[j]来取代dp[i-1][x]，随着j的改变不断更新mx数组就可以降低一层循环。

这样动态转移方程就变为：dp[i][j]=max(dp[i][j-1]+a[j],mx[j-1]+a[j]);

滚动数组mx[j]表示把数组a的前x个数分成i-1个子段的和的最大值

#include<iostream>
#include<string.h>
#define ll long long
using namespace std;
ll dp[1000005],mx[1000005],a[1000005];
//dp[j]是将数组前j个数分成i组的最大和，mx[j]是将数组a中前j个数分成任意组的最大和的最大值
ll max(ll a,ll b)
{
    return a>b?a:b;
}
int main()
{
    ll n,m,sum;
    while(~scanf("%lld%lld",&m,&n))
    {
        memset(dp,0,sizeof(dp));
        memset(mx,0,sizeof(mx));
        for(int i=1;i<=n;i++)
            scanf("%lld",&a[i]);

        for(int i=1;i<=m;i++)
        {
            sum=-99999999999999999;
            for(int j=i;j<=n;j++)
            {
                dp[j]=max(dp[j-1]+a[j],mx[j-1]+a[j]);
                mx[j-1]=sum;//sum是将数组a的前j-1个数分成i组的最大和
                sum=max(dp[j],sum);//更新sum,为下一次更新mx[j]准备
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}