HDU - 1024 Max Sum Plus Plus 最大m段子段和+滚动数组优化

给定n个数字，求其中m段的最大值（段与段之间不用连续，但是一段中要连续）

例如：2 5 1 -2 2 3 -1五个数字中选2个，选择1和2 3这两段。

dp[i][j]从前j个数字中选择i段，然后根据第j个数字是否独立成一段，可以写出

状态转移方程:dp[i][j]=max(dp[i][j-1]+num[j],max(dp[i-1][k])+num[j])

这里的max（dp[i-1][k]）代表的拥有i-1段时的最大值，然后再加上num[j]独立成的一段。

但是题目中没有给出m的取值范围，有可能爆内存和爆时，都需要处理一下。

对于防爆内存：注意到dp[i][*]只和dp[i][*],dp[i-1][*]，即当前状态只和前一状态有关，可以用滚动数组优化（资料）。

对于防爆时：既然max（dp[i-1][k]）代表的拥有i-1段时的最大值，我们可以用一个数组pre储存之前的最大值

状态转移方程：dp[i][j]=max(dp[i][j-1]+num[j],pre[j-1]+num[j])发现不关i什么事，于是乎

最后的状态转移方程：dp[j]=max(dp[j-1]+num[j],pre[j-1]+num[j])

#include <iostream>

#include <algorithm>

using namespace std;

const int N=;

const int INF=0x3f3f3f3f;

int num[N],pre[N],dp[N];

int main(){

    int n,m;

    while(scanf("%d %d",&m,&n)!=EOF){

        for(int i=;i<=n;i++) scanf("%d",&num[i]),dp[i]=,pre[i]=;

        int MAX;

        dp[]=pre[]=;

        for(int i=;i<=m;i++){

            MAX=-INF;

            for(int j=i;j<=n;j++){//这里以i开始，因为最少要i个数字才能支撑i段

                dp[j]=max(dp[j-]+num[j],pre[j-]+num[j]);

                pre[j-]=MAX;

                MAX=max(MAX,dp[j]);

            }

        }

        printf("%d\n",MAX);

    }

    return ;

}

巴特西

HDU - 1024 Max Sum Plus Plus 最大m段子段和+滚动数组优化

最新文章

热门文章