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

6

8

 

题意：输入有多个样例，每个样例输入只有一行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
       
        #include
        
         #define ll long longusing 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优化

对动态转移方程：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
       
        #include
        
         #define ll long longusing 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<
         
          <