hdu 1024 Max Sum Plus Plus

链接

[https://vjudge.net/contest/256508#problem/B]

题意

就是让你从有n个数中选出m个子段
每个字段必须连续。求最大和

分析

很容易想到状态的定义和状态转移方程

 dp[i][j]=max(dp[i][j-1],max(dp[i-1][k]))+a[j]; i-1<k<j
dp[i][j]表示前i个数在选取第i个数的前提下分成j段的最大值，其中1<=j<=i<=n && j<=m，

但是由于m是未知所以开二维的会容易MLE，所以只能压缩空间
当前i段状态只和前面i-1段有关。用一个一维的保存max(dp[i-1][k])
就行。很经典的滚动数组应用,必须掌握啊，有时还可以降低时间复杂度
由于自己比较愚蠢所以看了好久。学到了

看代码

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=1e6+10;
int dp[N],pre[N],a[N];
int main(){
    int n,m;
    //freopen("in.txt","r",stdin); 
    while(~scanf("%d%d",&m,&n)){
        for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        dp[i]=0;
        pre[i]=0;
    }
    int ma;
    for(int i=1;i<=m;i++)
    {
        ma=-1e9;
        for(int j=i;j<=n;j++)
        {    //dp[i][j]=max(dp[i][j-1],max(dp[i-1][k]))+a[j]; i-1<k<j
        //dp[i][j]表示前i个数在选取第i个数的前提下分成j段的最大值，其中1<=j<=i<=n && j<=m，
            dp[j]=max(dp[j-1],pre[j-1])+a[j];
            //上面的pre[j-1]代表到a[j-1]为止分成i-1段的最大和(a[j-1]不一定得选)
            //dp[j]代表选了a[j]之后分成i段的最大和
            pre[j-1]=ma; 
            //pre[j-1]=ma;是代表到a[j-1]为止分成i段的最大和(a[j-1]不一定得选) 
            //下面 ma=max(dp[j],ma); 体现了不一定选 
            ma=max(dp[j],ma); 
        }
    }
    printf("%d\n",ma);
    }
    return 0;
}

hdu 1024 Max Sum Plus Plus

原文：https://www.cnblogs.com/mch5201314/p/10626572.html