如果对于某件事情没有思路，就先模拟一下如果发生了什么事请会产生什么样的性质

C. First or Second

时间限制：每个测试点 2 秒内存限制：每个测试点 256 MB

问题描述

有 $n$ 个孩子站成一排，第 $i$ 个孩子的“善良值”是 $a_i$ 。圣诞老人正在决定哪些孩子属于“好孩子”名单，哪些属于“淘气”名单。

一个整数 $X$ 初始被设为 $0$ 。圣诞老人将恰好执行 $n-1$ 次以下操作： 1. 选择队列中的第一个或第二个孩子，并将其从队列中移除。 2. 令 $w$ 为被选中的孩子的善良值。 3. 如果选中了第一个孩子，则将其加入好孩子名单，并将 $w$ 加到 $X$ 上。 4. 如果选中了第二个孩子，则将其加入淘气名单，并将 $w$ 从 $X$ 中减去。

请注意，在所有操作之后，恰好有一个孩子未被分配到任何名单。

请确定圣诞老人在完成所有 $n-1$ 次操作后，可以获得的 $X$ 的最大可能值。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ $(1 \le t \le 10^4)$ 。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ $(2 \le n \le 2 \cdot 10^5)$ —— 孩子的数量。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ $(-10^9 \le a_i \le 10^9)$ —— 每个孩子的善良值。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$ 。

输出格式

对于每个测试用例，输出一个整数 —— 圣诞老人在完成所有 $n-1$ 次操作后，可以获得的 $X$ 的最大可能值。

样例输入

7
2
2 -3
4
1 4 3 4
4
-4 2 3 -6
5
-2 -3 4 10 -9
5
-12345678 -1000000000 -999999999 1000000000 -999999999
2
-7 1
5
7 -6 -1 -8 -8

样例输出

样例说明

在第一个测试用例中，圣诞老人将恰好执行一次操作。如果他选择第一个孩子，他需要将 $a_1=2$ 加到 $X$ 上，得到 $X=2$ ；如果他选择第二个孩子，他需要从 $X$ 中减去 $a_2=-3$ ，得到 $X=3$ 。因此，答案是 $3$ 。

在第二个测试用例中，最优策略是在所有三次操作中都选择第一个孩子。 $X$ 的值将为 $1+4+3=8$ 。

在第三个测试用例中，以下是一个最优操作序列： | # | 操作类型 | 操作后剩余的孩子（善良值） | 操作后的 $X$ | |---|----------|----------------------------|--------------| | 0 | — | $[-4, 2, 3, -6]$ | 0 | | 1 | 选第一个 | $[2, 3, -6]$ | -4 | | 2 | 选第一个 | $[3, -6]$ | -2 | | 3 | 选第二个 | $[3]$ | 4 |

在第四个测试用例中，以下是一个最优操作序列： | # | 操作类型 | 操作后剩余的孩子（善良值） | 操作后的 $X$ | |---|----------|----------------------------|--------------| | 0 | — | $[-2, -3, 4, 10, -9]$ | 0 | | 1 | 选第二个 | $[-2, 4, 10, -9]$ | 3 | | 2 | 选第一个 | $[4, 10, -9]$ | 1 | | 3 | 选第一个 | $[10, -9]$ | 5 | | 4 | 选第一个 | $[-9]$ | 15 |

第一次

// Problem: CF 2178 C
// Contest: Codeforces - Good Bye 2025
// URL: https://codeforces.com/contest/2178/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false);cin.tie(nullptr);
#define int long long 

void solve(){
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    stack<int> s;
    for(int i=n-1;i>=0;i--){
        s.push(a[i]);
    }
    int ans=0;
    while(s.size()>1){
        int u=s.top();
        s.pop();
        int v=s.top();
        s.pop();
        if(u+v>0){
            ans+=u;
            s.push(v);
        }else{
            ans+=(-v);
            s.push(u);
        }
    }
    cout<<ans<<endl;
    return ;
}

signed main(){
    //ios;
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

你的代码问题分析

你的第一版代码使用了一个贪心策略（栈模拟），每次只看最后两个元素 $u, v$ ，谁大保留谁。

为什么是错的？

这是一个经典的“局部最优 $\neq$ 全局最优”陷阱。

在步骤 $i$ 选择“保留 $u$ 还是保留 $v$ ”，不仅仅取决于 $u$ 和 $v$ 的大小，还取决于保留下来的那个数在未来能产生多大的价值。如果你现在贪心地保留了一个较大的数，但它导致后面一个超级大的数被迫变成了减项（被选中为第二个），那就亏大了。

反例：

输入：100 -200 1000

你的贪心逻辑：
- 栈顶取出 -200 和 1000。
- $u=-200, v=1000$ 。 $u+v = 800 > 0$ 。
- 结果 $+(-200)$ ，保留 1000。栈变成 [100, 1000]。
- 下一步 100 和 1000，结果 $+100$ 。
- 总分：-100。
最优解：
- 先选第二个（即 -200），产生 $-(-200) = +200$ 。剩余 [100, 1000]。
- 再选第一个（即 100），产生 $+100$ 。剩余 [1000]（幸存者，不计分）。
- 总分：300。

显然，你的贪心策略亏了很多。

正确思路：后缀 DP（线性优化）

这个问题可以转化为一个后缀动态规划问题。我们需要倒着思考：我们如何处理数组的后缀 $a[i \dots n]$ ，使得收益最大？

1. 公式推导

对于当前的排头兵 $a[i]$ ，我们有两种选择：

立刻选它（作为第一个）：

收益 $= a[i] + \text{处理剩余后缀 } a[i+1 \dots n] \text{ 的最大收益}$

即： $a[i] + dp[i+1]$
选它的下一个（作为第二个）：

这意味着 $a[i]$ 暂时没被选，而 $a[i+1]$ 被作为负项移除了。之后我们面对的是 $a[i]$ 和 $a[i+2]$ 。

如果我们沿着这条路一直走下去（一直选第二个），直到在第 $k$ 个位置决定选 $a[i]$ 为止，这一串操作的数学形式其实是：

$a[i] - a[i+1] - a[i+2] - \dots - a[k-1] + dp[k]$

利用后缀和 $S[i] = \sum_{j=i}^{n} a[j]$ ，上面的式子可以化简为：

$= a[i] - (S[i+1] - S[k]) + dp[k]$

$= a[i] - S[i+1] + (dp[k] + S[k])$

还有一种特殊情况是 $a[i]$ 一直留到了最后成为幸存者，那么收益就是：

$-a[i+1] - a[i+2] - \dots - a[n] = -S[i+1]$

2. 最终的 DP 转移方程

合并以上情况，对于位置 $i$ ，最大收益 $dp[i]$ 是：

$dp[i] = \max( -S[i+1], \quad a[i] - S[i+1] + \max_{k > i} (dp[k] + S[k]) )$

这里有个关键的优化点：我们需要频繁查询 $\max_{k > i} (dp[k] + S[k])$ 。

我们可以维护一个变量 $M$ ，表示当前后缀中最大的 $(dp[k] + S[k])$ 。

化简后的 $O(N)$ 算法：

从后往前遍历 $i$ ：

$dp[i] = -S[i+1] + \max(0, a[i] + M)$
更新 $M = \max(M, dp[i] + S[i])$

AC 代码

C++

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

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i=0; i<n; i++){
        cin >> a[i];
    }

    // 1. 预处理后缀和 S
    // S[i] 表示 a[i]...a[n-1] 的和
    vector<int> S(n + 1, 0);
    for(int i = n - 1; i >= 0; i--){
        S[i] = S[i+1] + a[i];
    }

    // 2. 倒序 DP
    // dp 表示当前后缀的最大收益
    // M 表示 max(dp[k] + S[k]) 的维护值

    // 初始化：对于最后一个元素 a[n-1]
    // 它是唯一的元素，无法操作，只能幸存，所以 dp[n-1] = 0
    // M 初始为 dp[n-1] + S[n-1] = 0 + a[n-1]

    int dp = 0;
    int M = a[n-1]; 

    // 从倒数第二个元素开始往前推
    for(int i = n - 2; i >= 0; i--){
        // 公式：dp[i] = -S[i+1] + max(0, a[i] + M)
        // max(0, ...) 是因为如果选a[i]都不划算，不如让a[i]直接幸存（对应-S[i+1]）
        int current_dp = -S[i+1] + max(0LL, a[i] + M);

        // 更新 M
        M = max(M, current_dp + S[i]);

        dp = current_dp;
    }

    cout << dp << endl;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

总结

数据结构选择： 这题不需要复杂的栈或队列，只需要数组配合后缀和。
核心逻辑： 这是一个决策问题（何时把当前的排头兵加进去，何时把它留着去抵消后面的负数），倒序 DP 可以完美解决这种具有“未来依赖性”的问题。
复杂度： $O(N)$ 时间， $O(N)$ 空间（甚至可以优化到 $O(1)$ 空间，只存 $S$ 和 $M$ 的滚动值）。

这思路妙啊

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

void solve(){
    int n;
    cin >> n;
    vector<int> a(n+3),suf(n+3,0),pre(n+3,0);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=2;i<=n;i++){
        pre[i]=pre[i-1]+abs(a[i]);
    }
    for(int i=n;i>0;i--){
        suf[i]=suf[i+1]-a[i];
    }
    int ans=suf[2];
    for(int i=2;i<=n;i++){
        ans=max(ans,a[1]+pre[i-1]+suf[i+1]);
    }
    cout<<ans<<endl;
    return ;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}