C - Max Sum Plus Plus HDU

用二位数组dp[i][j]记录组数为i，前j个数字的最大子段和。

转移方程dp[i][j]=min(dp[i][j-1],dp[i-1][k])+arr[j]，方程表示的是考虑到第j个数，可以把它直接加入到第i组，也可以作为第i组的开头，如果作为第i组的开头，就要考虑第i-1组该以哪个数结尾。直接枚举k，k从(i-1)到j-1。

优化：因为题目n值范围过大，显然二维数组不行。而d[i][x]只与d[i-1][x]有关，所以可以将其降低至一维。即dp[j]表示前j个数所分段后的和。因为dp[i-1][k]的取值需要一重循环，极有可能导致超时，所以使用数组max[]，存储当前层的最大值，以供下一层求值使用。dp[j] = max(dp[j-1] + a[j], max[j-1] + a[j])

#include<bits/stdc++.h>

using namespace std;

const int N=1e6+;

const int INF=1e9+;

int dp[N];

int arr[N];

int ma[N];

int main(){

    int n,m;

    while(cin>>m>>n){

        memset(ma,,sizeof ma);

        for(int i=;i<=n;i++)

            scanf("%d",&arr[i]);

        int tmp;

        for(int i=;i<=m;i++){//第i组

            tmp=-INF;

            for(int j=i;j<=n;j++){//考虑第j个人

                dp[j]=max(dp[j-],ma[j-])+arr[j];

                ma[j-]=tmp;//此时tmp的值还没有更新，所以应该是当j=j-1时的最大值

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

            }

        }

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

    }

    return ;

}

巴特西

C - Max Sum Plus Plus HDU - 1024

最新文章

热门文章