题意重述

给定一个由 "+" 和 "-" 组成的字符串 $s$，长度 $n$。
定义数组 $a$：

$$a_i = \begin{cases} 1, & s_i = \text{`+'}\\ -1, & s_i = \text{`-'} \end{cases} $$

我们要将 $a$ 分成若干个非空连续子数组 $b_1, b_2, \dots, b_k$（即 $b_1 + b_2 + \dots + b_k = a$，$+$ 表示数组连接）。

对每个子数组 $c$（长度为 $m$）定义罚分：

$$p(c) = |c_1 + c_2 + \dots + c_m| \cdot m$$

总罚分：

$$P = p(b_1) + p(b_2) + \dots + p(b_k)$$

问：在最优拆分下，$P$ 的最小值是多少。

---

关键观察

1. 罚分的下界

定义一个替代罚分函数：

$$p_2(l, r) = \left| \sum_{j=l}^r a_j \right|$$

即忽略长度因子。

显然：

$$p_2(l, r) \le p(l, r)$$

因为 $|sum| \cdot m \ge |sum|$ 当 $m \ge 1$。

对于替代罚分函数，总罚分为 $\sum |\text{subarray sum}|$。
由于对整数 $x, y$ 有 $|x| + |y| \ge |x + y|$，因此最优策略是不拆，直接取整个数组：

$$\min \sum |\text{subarray sum}| = |a_1 + a_2 + \dots + a_n| $$

因此原问题的答案 $P_{\min} \ge |a_1 + a_2 + \dots + a_n|$。

---

2. 可达性证明

我们想证明：存在一种拆分，使 $P = |a_1 + a_2 + \dots + a_n|$。

第一步：对称性
若把 $a$ 中所有元素取反（+ 变 -，- 变 +），每个子数组的绝对值不变，所以答案不变。
因此可假设 $S = \sum a_i \ge 0$。

---

第二步：构造

• 若 $S = 0$，直接整个数组作为一个子数组，罚分 $|0| \cdot n = 0$，达到下界 $0$。

• 若 $S > 0$：
  寻找最大的 $i$，使前缀和 $a_1 + \dots + a_i = 0$。
  将 $[1, i]$ 作为一个子数组，它的和是 $0$，罚分 $0$。
  下一个元素 $a_{i+1}$ 必须是 $+1$（否则若它是 $-1$，从 $0$ 开始再出现负值，为了最终和 $S>0$，后面必须出现更大的正和，会使得另一个前缀和再次为 $0$，这与 $i$ 最大矛盾）。

  所以 $a_{i+1} = 1$。
  我们将 $[i+1, i+1]$ 作为一个长度为 $1$ 的子数组，其和为 $1$，罚分 $1 \cdot 1 = 1$。

  剩余部分 $[i+2, n]$ 的总和变为 $S - 1$。

重复上述过程：每次切出一个 $0$ 和的子数组（可能空）和一个 $+1$ 单元素子数组，总罚分增加 $1$，剩余总和减少 $1$，直到总和减到 $0$。

最终总罚分 $= S = |S|$。

---

3. 总结公式

因此，最小罚分就是整个数组的总和的绝对值：

$$\text{ans} = \left| \sum_{i=1}^n a_i \right|$$

其中 $a_i = 1$ 对应 '+'，$a_i = -1$ 对应 '-'。

---

代码实现

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

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        string s;
        cin >> n >> s;
        
        int sum = 0;
        for (char c : s) {
            sum += (c == '+') ? 1 : -1;
        }
        
        cout << abs(sum) << '\n';
    }
    return 0;
}

---

复杂度分析

• 时间复杂度：$O(n)$ 对每个测试用例。
• 空间复杂度：$O(1)$ 除了存储字符串。

---

验证样例

1. "+"：$a = [1]$，总和 $1$，答案 $1$ ✅
2. "-----"：$a = [-1,-1,-1,-1,-1]$，总和 $-5$，绝对值 $5$ ✅
3. "+-+-+-"：$a = [1,-1,1,-1,1,-1]$，总和 $0$，答案 $0$ ✅
4. "--+++++++-"：$a = [-1,-1,1,1,1,1,1,1,1,-1]$，总和 $(-1-1)+(7 \times 1) -1 = 4$，答案 $4$ ✅
5. "+---++++-+++++---++-"：计算可得总和绝对值 $4$ ✅