题解：P16230 [蓝桥杯 2026 省 A] 综合应变指标

lcyxds · 2026-05-11 09:08:11 · 题解

考虑绝对值正负分类（不会让答案变大/小），DP 设计八个状态：当前在第 0/1/2/3 段当前段取正/负。转移分两类：开新段和延续之前段即可。

可以滚动数组优化，时间复杂度 \Theta\!\left(n\right)，空间复杂度 \Theta\!\left(1\right)。

#include <iostream>
#include <cstring>
#include <array>
#include <algorithm>

using namespace std;

using ll = long long;

const ll INFLL = 0x3f3f3f3f3f3f3f3fll;
const ll NINFLL = 0xc0c0c0c0c0c0c0c0ll;

int n;

void Solve() {
    cin >> n;
    array<ll, 8> dp;
    dp.fill(NINFLL);
    dp[0] = 0;
    dp[1] = 0;
    while (n--) {
        int a;
        cin >> a;
        dp[7] = max({dp[4], dp[5], dp[7]}) - a;
        dp[6] = max({dp[4], dp[5], dp[6]}) + a;
        dp[5] = max({dp[2], dp[3], dp[5]}) - a;
        dp[4] = max({dp[2], dp[3], dp[4]}) + a;
        dp[3] = max({dp[0], dp[1], dp[3]}) - a;
        dp[2] = max({dp[0], dp[1], dp[2]}) + a;
        dp[1] -= a;
        dp[0] += a;
    }
    cout << max(dp[6], dp[7]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // int T;
    // cin >> T;
    // while (T--) {
    //     Solve();
    // }
    Solve();
    return 0;
}