HDU 1024 Max Sum Plus Plus(DP+最大M子段和)

2018-03-31

Max Sum Plus Plus

题意

n个数字，选m组，使得SUM最大。

思路

dp[i][j]=max(dp[i][j-1]+a[j],max(dp[i-1][k])+a[j]) (0<k<j)。

dp[i][j-1]+a[j]表示的是前j-1分成i组，第j个必须放在前一组里面。

max( dp[i-1][k] ) + a[j] )表示的前（0<k<j）分成i-1组，第j个单独分成一组。

但是题目的数据量比较大，时间复杂度为n^3，n<=1000000，显然会超时，继续优化。

max( dp[i-1][k] ) 就是上一组 0….j-1 的最大值。我们可以在每次计算dp[i][j]的时候记录下前j个
的最大值用数组保存下来，这样时间复杂度为 n^2。

(1)节省时间

由基本思路，我们可以知道，dp[i][j]=max(dp[i][j-1]+num[j],dp(i-1,t)+num[j])，其中i-1<=t<=j-1.我们只要找到dp[i][j-1] 和dp[i-1][t]的最大值加上num[j]即为dp[i][j].所以，定义一个数组pre_max[n]，用pre_max[j-1]来表示求解dp[i][j]时dp[i-1][t]的最大值,则dp[i][j]=max(pre_max[j-1],dp[i][j-1])+num[j]。特别注意，pre_max[n]这个位置的存储空间是始终用不到的，因此可以用来存储其他数值，在接下来会用到。在求解dp[i][j]的同时，我们可以计算出dp[i][t];i<=t<=j的最大值，这个最大值在计算dp[i+1][j+1]的时候需要作为pre_max[j]的形式被使用，我们先把它存在pre_max[n]中。
你可能会问：为什么不把它直接放在pre_max[j]中呢？因为你接下来需要计算dp[i][j+1]的值，需要用到pre_max[j]中原来的值，如果你把它存在这里，就会覆盖掉计算dp[i][j+1]所需要的那个值。所以，先把它放在pre_max[n]中。当我们计算完dp[i][j+1]之后，就会发现pre_max[j]中的值已经没有用处了，我们可以把它更新为计算dp[i+1][j+1]所需要的那个值，即之前放在pre_max[n]中的那个值，即执行pre_max[j]=pre_max[n]。这样我们就节省了计算最大值时付出的时间代价。

(2)节省空间

通过时间的节省，我们突然间发现程序执行结束后pre_max[n]的值即为最后的结果，pre_max[n]数组才是我们希望求解的，dp[m][n]这个庞大的数组已经不是那么重要了，因此，我们现在用整型数tmp来代替dp[m][n]，用来临时存储dp[i][j]的值，作为求解pre_max[n]的中介。这样就节省了dp[i][j]占用的极大的空间。

看！代码

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int dp[1000010],MAX[1000010],a[1000010];
int main()
{
    int n,m;
    int maxx;
    while (~scanf("%d%d",&m,&n))
    {
        memset(dp,0,sizeof(dp));
        memset(MAX,0,sizeof(MAX));
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(int i=1;i<=m;i++)
        {
            maxx=-INF;
            for(int j=i;j<=n;j++)
            {
                dp[j]=max(dp[j-1]+a[j],MAX[j-1]+a[j]);
                MAX[j-1]=maxx;
                maxx=max(maxx,dp[j]);
            }
        }
        printf("%d\n",maxx);
    }
    return 0;
}

[][][][]