DP 详解

DP 概述

DP（Dynamic programming，全称动态规划），是一种基于分治，将原问题分解为简单子问题求解复杂问题的方法。

动态规划的耗时往往远少于朴素（爆搜）解法。

动态规划 and 递归

之前说过，动态规划也是分治思路，而递归更是传统的分治思路，但时间复杂度却大相径庭，为什么呢？

动态规划是

状态的定义

前言：空间换时间

很简单的名字，即为使用空间的代价来确保不会超时。

状态？

状态，通俗来讲就是你 分类讨论就是将问题通过不同的结果 / 形式 / 不同点分成几类逐个解决。

例题二思路

既然说到分类讨论我们先来分个类。

\(\max(\sum_{i = 1}^{N} A_i) = \begin{cases} C > 0 & \max(\sum_{i = L}^{R} A_i) \times C \\\\ C < 0 & \min(\sum_{i = L}^{R} A_i) \times C \end{cases}\)

最大最小怎么使用 \(O(N)\) 求？Bingo！最大 / 最小 子段和即可。

最后比一下就好了。

完整 Code：

#include <bits/stdc++.h> 
using namespace std;

#define ll long long
int n;
ll c;
ll a[100005];
ll solve()
{
    ll original_sum = 0;
    for (int i = 1; i <= n; ++i)
        original_sum += a[i];

    ll dp_max[100005], dp_min[100005];
    dp_max[1] = a[1];
    dp_min[1] = a[1];

    ll maxx = dp_max[1];
    ll minn = dp_min[1];

    for (int i = 2; i <= n; i++)
    {
        dp_max[i] = max(a[i], dp_max[i - 1] + a[i]);
        dp_min[i] = min(a[i], dp_min[i - 1] + a[i]);
        maxx = max(maxx, dp_max[i]);
        minn = min(minn, dp_min[i]);
    }

    ll res = max((c - 1) * maxx, (c - 1) * minn);
    ll ans = original_sum + res;
    return ans;
}

int main()
{
    cin >> n >> c;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    cout << solve() << endl;
    return 0;
}