HDU 1024 Max Sum Plus Plus

用户1624346

发布于 2018-04-17 16:20:20

9230

发布于 2018-04-17 16:20:20

文章被收录于专栏：calmound

http://acm.hdu.edu.cn/showproblem.php?pid=1024

题意：可不连续的m个子段的最大和

分析：首先由于n很大，所以需要运用滚动数组，其次单个值也不小所以得考虑int64 接下来就是动态规划的思路了，这道题想了大概一上午没什么好思路，只想到第j个数要不属于第i组，要不独自成组所以我只想到的转移方程为dp[i,j]=max(dp[i-1,j-1],dp[i][j-1])+num[j] 其中dp[i,j]为j个数分成i组的时候其最大和是多少 dp[i-1,j-1]表示第j个数独自成组 dp[i,j-1]表示第j个数合到前一个数这个思路只对了一半，错在当j要独自成组的时候，并不一定dp[i-1,j-1]就是最大值，还有可能j-1这个数没有要， dp[i-1,j-2] 或者dp[i-1,j-3]是最大的根据这个，我又重新找出dp[i-1,k]（i-1<=k<j）中的最大值，但是此时的dp循环是三个for循环了，果断超时。后来看了别人代码，才了解定义一个MAX，一直记录着对于当前i的某个j的最大dp[i-1,k]，由于对于j来说，必定从i开始循环过来的，所以MAX就是记录以前的最大值。

然后还要注意的是，循环当前i的时候，需要剩下m-i个数的，让后面的人能够有数可用

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int MN=1000010;
const int INF=999999999;
#define LL long long
//dp[i,j]表示i个组里有j物品的最大和
LL dp[2][MN];
int num[MN];

int main()
{
    int i,j,n,m,k;
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        for(i=1;i<=n;i++)
        {
            dp[0][i]=dp[1][i]=0;
            scanf("%d",&num[i]);
        }
        dp[0][0]=dp[1][0]=0;
        int t=1;
        for(i=1;i<=m;i++)
        {
            dp[t][i]=dp[1-t][i-1]+num[i];
            LL MAX=dp[1-t][i-1];
            for(j=i+1;j<=n-(m-i);j++)
            {
                MAX=max(MAX,dp[1-t][j-1]);
                dp[t][j]=max(MAX,dp[t][j-1])+num[j];
            }
            t=1-t;
        }
        t=1-t;
        LL MAX=-INF;
        for(i=m;i<=n;i++)
        {
            if(MAX<dp[t][i]) MAX=dp[t][i];
        }
        printf("%I64d\n",MAX);
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2013-09-04 ，如有侵权请联系 cloudcommunity@tencent.com 删除

php