ACM模版

描述

题解

不得不说，这是一道十分有趣的dp，同时也刷新了我对dp的认知，我原来的思维过于局限了。

以下为某大牛思路：

用两个数组，pre[MAXN]和dp[MAXN]，
首先m次循环，第x次循环代表的是把整个序列分成x个子段所能得到的最大x子段和。
pre[i]数组记录的是，从第1个数到第i个数被分成x个子段所能得到的最大子段和。
假设当前已分成了x个子段(即最外层循环执行了x次)，然后需要执行第x+1次时，
则dp[i]的转移是从下列两种情况取max值：
1.前i-1个数分为x个子段得到的最大和pre[i-1]加上单独把input[i]作为第x+1个子段的开头；
2.从前i-1个数中已经分出了x+1个子段，且第x+1个子段的尾部需要加上input[i]，即dp[i-1]+input[i]。

是时候来一场dp的专项训练了~(≧▽≦)/~

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 5050;
const int MIN_INF = -0x3f3f3f3f;

ll dp[MAXN];
ll input[MAXN];
ll pre[MAXN];

int n, m;

int main()
{
    scanf("%d%d", &n, &m);

    dp[0] = MIN_INF;
    pre[0] = 0;

    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &input[i]);
        pre[i] = 0;
        dp[i] = MIN_INF;
    }

    while (m--)
    {
        ll ans = MIN_INF;
        for (int i = 1; i <= n; i++)
        {
            if (i == 1)
            {
                dp[i] = pre[i - 1] + input[i];
            }
            else
            {
                if (dp[i - 1] > pre[i - 1])
                {
                    dp[i] = dp[i - 1] + input[i];   // 第i个数与它的上一个数在同一子段内
                }
                else
                {
                    dp[i] = pre[i - 1] + input[i];  // 从第i个分出一个新的子段
                }
            }
            // dp[i] = max(dp[i - 1], pre[i - 1]) + input[i]; 或者直接这么取值也可
            pre[i - 1] = ans;
            ans = max(ans, dp[i]);
        }
        pre[n] = ans;
    }
    printf("%lld\n", pre[n]);

    return 0;
}