Oiclass P3314 题解

这道题从题面就可以看出是经典的最长不下降子序列

对于这道一点都不简单的最长连续子序列和的模板题，我们还是直接暴力，代码：

#include <iostream>

using namespace std;

int ans, n, a[1009];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] += a[i - 1];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            if (i < j) {
                ans = max(ans, a[j] - a[i - 1]);
            }
        }
    }
    cout << ans;
}

额，\(\Huge 搞错了，进入正题\)

这道题的正解是采用 DP 的方法，时间复杂度为 \(\Large O(n)\) 相比暴力的 \(\Large O (n^2)\) 可以说是质的飞跃。OK，接下来就是经典的不能再经典的五步

1. 划分阶段

我们将阶段划分为以各个数字为序列的末尾时的最优解

2. 确认状态和状态变量

在这道题目中，我们使用一个数组 \(a\) 来保存原始数列， 数组 \(f\) 来保存状态

3. 确认决策并写出状态转移方程

我们的决策很简单，确定以这个位置的数为数列末位时将其加入上一个数的数列还是新建一个数列能使和更大就行了，也就是说如果 \(f_{i-1} < 0\) , 应当选择 \(f_i = a_i\) ，也就是新建数列。当 \(f_{i-1} ≥ 0\) ，选择 \(f_i = f_{i-1} + a_i\) ，也就是将 \(a_i\) 合并入 \(f_{i -1}\) 所在的数列。 简单写出方程是这样的： \[ f_i=\max\left(f_{i-1},\ 0\right) + a_i \] 就这么简单，实现也是一样简单

4. 初始状态

简单分析可以得到，有定值的状态就是第一个（\(f_1\)） 因为它是数列的第一个，所以他的前面一定没有数列，他的最大值一定是它本身，即： \[ f_1 = a_1 \]

5. 实现

通过上面的操作，我们已经明白如何确定每一种状态的最优解了，那么招到全局最优解也是易如反掌的事情了，我们只需要在左右局部最优解里找到一个最大的就行了，我们可以直接模拟，代码简单，就不贴出来了。当然为了更加优雅，也可以把 \(a\) 和 \(f\) 合并为一个数组，同时在输入的过程中直接进行计算得到答案。好的，这里就产生一个问题了：为什么我可以直接在输入个过程中进行计算呢？这里利用了 DP 的无后效性，也就是说后面的数据对前面算出来的最优解是不会产生影响的，这也是这道题可以用 DP 求解的原因。

OK，讲了这么多，该贴代码了，如下：

#include <iostream>

using namespace std;

int ans, n, a[1009];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i - 1] > 0) {
            a[i] += a[i - 1];
        }
        ans = max(ans, a[i]);
    }
    cout << ans;
}

搞定收工