【题解】最大 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]=\begin{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\n",dp[n]);

    }

}

巴特西

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

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

【题目描述】

【分析】

【Code】

最新文章

热门文章