【题解】最大 M 子段和 Max Sum Plus Plus [Hdu1024] [51nod1052]

传送门：最大 (M) 子段和 (Max) (Sum) (Plus) (Plus) ([Hdu1024]) ([51nod1052])

【题目描述】

给出一个长度为 (N) 的序列，将这 (N) 个数划分为互不相交的 (M) 个子段，并使得 (M) 个子段的和最大。

【样例】

样例输入：
7 2
-2
11
-4
13
-5
6
-2

样例输出：
26

【数据范围】

(100\%) (1 leqslant N leqslant 10^6)

【分析】

在 (51nod) 里面这道题的数据水出了一种极其诡异的境界，首先是它题目里瞎扯的一个特判没毛用，其次，我尝试了不下 (10) 种错误写法（包括不同题意所造成的不同写法），居然全对 (...)

设 (dp[i][j]) 表示使用前 (j) 个数划分了 (i) 段的最大和。
由于所选段不一定要连续，所以 (dp[i][j]=dp[i][j-1])，即第 (i) 段不选 (a[j]) 的情况。

如果要选 (a[j]) ，那么应该是从 (a[j]) 往前选出连续的一段 ([k+1,j]) 作为第 (i) 段，即 (dp[i][j]=max{dp[i-1][k]+S[j]-S[k]]})，其中 (k in[i-1,j-1],) 为了保证这之后剩下的数可以足够选完 (m) 段，需要满足 (i-j geqslant m-n) 即 (j in [i,n-m+i])，(S[i])为 (a[i]) 的前缀和。

开一个滚动数组 (f) 优化掉第一维，就成了酱紫： (dp[j]=egin{cases} max_{k=i-1}^{j-1}{f[k]-S[k]]}+S[j] & j=i\max{dp[j-1],{max_{k=i-1}^{j-1}{f[k]-S[k]]}+S[j]}} & j>i end{cases})

对于上面 (j=i) 的情况，实际操作时，可以特判，也可以直接 (dp[i-1]=-inf) 。
后面那一大堆求最大值的表达式可以直接用一个变量 (maxs) 来保存，初始值为 (f[i-1]-S[i-1])，每求完一个 (dp[j])，就让其与 (f[j]-S[j]) 取个最大值，下一次 (dp[j+1]) 要使用 (maxs) 时，其维护的区间信息恰好为 ([i-1,(j+1)-1]) 。

【Code】

#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register LL
using namespace std;
const int N=1e6+3;
LL n,m,tmp,ans,maxs,S[N],f[N],dp[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
int main(){
    while(scanf("%lld%lld",&m,&n)!=EOF){
        for(Re i=1;i<=n;++i)in(S[i]),tmp+=(S[i]>0),S[i]+=S[i-1];
        memset(dp,0,sizeof(dp));
        memset(f,0,sizeof(f));
        for(Re i=1;i<=m;++i){
      	    for(Re j=1;j<=n;++j)f[j]=dp[j];
      	    maxs=f[i-1]-S[i-1];
      	    dp[i-1]=-1e18;
      	    for(Re j=i;j<=n-m+i;++j){
                dp[j]=max(dp[j-1],maxs+S[j]);
                maxs=max(maxs,f[j]-S[j]);
      	    }
        }
        printf("%lld
",dp[n]);
    }
}