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

zcEscortJ · 2026-07-24 19:39:09 · 题解

一个简单做法，在 O(n) 的时间复杂度内解决，空间复杂度是 O(8n)。使用轮换数组甚至可以把空间复杂度降到 O(1)。

设 dp_{i,j,k} 表示枚举到 i 时，前面共分了 j 段，且第 j 段的属性是 k(k\in\{0,1\}) 时答案的最大值。这里的属性表示的是第 j 个区间中每个值应该取 a_i 还是 -a_i。

这里再解释一下这个“属性”。对于一个区间，它对于答案的贡献无非两种，sum 和 -sum。此时，我们DP一个区间内的数对于答案的贡献就两种：全都加或者全都减。这时即使最后 sum 是负的，由于我们DP时取的是较大值，那么对应的 -sum 的状态也会被转移，从而覆盖掉不优的状态。

于是可以设计DP式。设 k=1 表示这段区间的每个值应该被加，k=0 表示区间内的值应该被减，则有：

答案是 \max(dp_{n,4,0},dp_{n,4,1})。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+5 ;
int n , dp[N][5][2] , x ;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n ;
    memset( dp , 0xcf , sizeof( dp ) ) ;//-inf
    dp[0][0][0] = dp[0][0][1] = 0 ;
    int x ;
    for( int i = 1 ; i <= n ; i ++ )
    {
        cin >> x ;
        for( int k = 1 ; k <= 4 ; k ++ )
        {
            dp[i][k][1] = max( { dp[i-1][k-1][0] , dp[i-1][k-1][1] , dp[i-1][k][1] } ) + x ;
            dp[i][k][0] = max( { dp[i-1][k-1][0] , dp[i-1][k-1][1] , dp[i-1][k][0] } ) - x ;
        }
    }
    cout << max( dp[n][4][0] , dp[n][4][1] ) ;
    return 0;
}