hduoj1024-Max Sum Plus Plus

发布于 2019-07-30  611 次阅读


问题传送门:

题意:

从一个数组取出不相交的m段,使得这m段之和加起来最大。
多组输入。n 最大是1e6.

分析:

这是一个动态规划问题,我们来定义dp[i][j] 表示的意义是:
在前 j 个元素中取 i 段的最大值,必须用 a[j] !
所以出现了两种情况:
  1. 让 a[j] 加入到当前的第 i 段中。
  2. 让 a[j] 单独成为第 i 段。
对于第一种情况, dp[i][j] = d[i][j-1] + a[j] ,这是显然的。
对于第二种情况, dp[i][j] = max(dp[i-1][0]~dp[i-1][j-1]) + a[i].
就是在前 j-1 个元素中,找到取出 i-1 段的最大值,然后让a[j] 作为第i段。

刚开始是这样想的:

for (int i = 1; i <= m; i++)
{
    for (int j = i; j <= n; j++)
    {
        int maxPre = dp[i-1][0]~dp[i-1][j-1];
        dp[i][j] = max(dp[i][j-1]+a[j], maxPre+a[j]);
    }
}
手动模拟一遍还是很容易理解的,虽然这样的思路没错,但是
n 的最大值是 1e6, 先不说时间复杂度,空间都不够存。所以必须优化成一维的。
看第一种情况,记录 i 的那一维是没有用的。
看第二种情况,用到的是在取出 i-1 的情况下的最大值
那我其实可以另外用一个数组专门去记录取出 i-1 段的最大值。
这样就把第一维去掉,降一维度。

代码:

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

const int MAXN = 1e6+10;
const int INF = 0x3f3f3f3f;

int a[MAXN];
int dp[MAXN];
int maxPre[MAXN];

int main()
{
    int m, n, maxn;
    while (cin >> m >> n)
    {
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
            dp[i] = 0, maxPre[i] = 0;
        } 
       for (int i = 1; i <= m; i++)
       {
           maxn = -INF;
           for (int j = i; j <= n; j++)
           {
               dp[j] = max(dp[j-1], maxPre[j-1]) + a[j];
               maxPre[j-1] = maxn;
               maxn = max(dp[j], maxn);
           }
       }
       cout << maxn << endl;  
    }    
    return 0;
}


Simple And Clear