最大M子段和 | 神奇的DP

题解

题目描述

N个整数组成的序列a[1],a[2],a[3],…,a[n]，将这N个数划分为互不相交的M个子段，并且这M个子段的和是最大的。如果M >= N个数中正数的个数，那么输出所有正数的和。
例如：-2 11 -4 13 -5 6 -2，分为2段，11 -4 13一段，6一段，和为26。

Input

第1行：2个数N和M，中间用空格分隔。N为整数的个数，M为划分为多少段。（2 <= N , M <= 5000)
第2 - N+1行：N个整数 (-10^9 <= a[i] <= 10^9)

Output

输出这个最大和

Input示例

7 2
-2
11
-4
13
-5
6
-2

Output示例

26

题解

设$dp[i][j]$表示将前$i$个数分成$j$段（且必须以第$i$个数结尾）的最大子段和。

$dp[i][j] = \max(dp[i-1][j] + a[i](若j紧连在上一段后面)）,$
               $\max_{k = 1}^{i-1} dp[k][j-1] + a[i](若j单独开一段))$

其中第二种情况可以处理出那个max，这样时间复杂度就是$O(n^2)$了。

那么如何压缩空间呢？

外层循环j，内层循环i，用一个pre数组单独维护$\max_{k = 1}^{i-1} dp[k][j-1] + a[i]$，一边做一边更新即可。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 5005, INF = 0x3f3f3f3f;
int n, m;
ll a[N], dp[N], pre[N]; 
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    for(int j = 1; j <= m; j++){
        dp[1] = a[1];
        for(int i = 2; i <= n; i++){
            dp[i] = max(dp[i - 1], pre[i - 1]) + a[i];
            if(i > 1) pre[i - 1] = max(pre[i - 2], dp[i - 1]);
        }
        pre[n] = max(pre[n - 1], dp[n]);
    }
    printf("%lld\n", pre[n]);
    return 0;
}