题解

先把选择片段的 DP 写出来。记 $W_i$ 为前 $i$ 个位置的收益和，$f_i$ 为前 $i$ 个位置能获得的最大收益。

若不选第 $i$ 个位置，就沿用 $f_{i-1}$。若选了它，最后一个片段必定形如 $(j,i]$，前面接上前 $j$ 位的最优方案，得到

$$f_j+W_i-W_j.$$

所以

$$f_i=\max\left(f_{i-1},\ \max_{(j,i]\text{ 能消空}}(f_j+W_i-W_j)\right).$$

片段不重叠已经由前缀 DP 保证了。剩下的难点集中在一个条件上，如何快速找出那些能和 $i$ 组成可消去片段的 $j$。

先看只有 a 和 A 的情况

把 a 记为 $+1$，A 记为 $-1$。一段串能消空，当且仅当它的和为零。

必要性很直接，删一对字符不会改变和。对于充分性，和为零的非空串同时含有两种字符，因此总能找到相邻的不同字符，删去后仍然和为零，继续删就能消空。

于是，若前缀和为 $D_i$，合法条件就是 $D_j=D_i$。把转移整理为

$$f_i=\max\left(f_{i-1},\ W_i+\max_{j<i,\ D_j=D_i}(f_j-W_j)\right),$$

每个前缀和只保存一个最大的 $f_j-W_j$ 就够了。

有两种互逆对时，分别统计两种字母的数量差还不够。abAB 的两种数量差都为零，却一对都删不了。这里必须保留字符的顺序。

用消去后的整个栈代替整数前缀和

从左往右扫描前缀，新字符若与栈顶互逆就弹栈，否则压栈。记处理前 $i$ 位后的栈中字符串为 $R_i$。

我们希望把前面的 $D_j=D_i$ 换成 $R_j=R_i$。需要证明

$$s_{j+1}\ldots s_i\text{ 能消空}\quad\Longleftrightarrow\quad R_j=R_i.$$

把所有可能的栈内容放在一棵树里，空栈为根。每个非空栈的父亲，就是删掉栈顶后的栈。

读入一个字符时，抵消会走向父亲，不抵消会走向某个儿子。这条树边来回走一次，恰好对应一对互逆字符。

如果片段能消空，每删掉相邻的一对互逆字符，就等于从行走路线中删掉一次沿同一条边的往返，最终位置不变。所有字符删完后没有移动，所以起点和终点必须相同，即 $R_j=R_i$。

反过来，如果两次的栈相同，这段字符就在树上形成了一次回到起点的行走。树里没有环，任何非空的这种行走，都要有一次沿同一条边立刻返回。对应的两个字符互逆，可以删去。删完后仍回到起点，反复执行就能把整段删空。

这样就把区间合法性变成了两个前缀状态相等。

栈不能每次都复制一份

若把整个栈字符串作为键，深度达到 $n$ 时，复制和比较的总开销可能变成二次。刚才那棵树可以直接建出来，用节点编号表示栈内容。

每个节点记录父亲、栈顶字符，以及四个字符分别对应的儿子。当前处于节点 $u$，读入字符 $c$。

• 若 $c$ 与栈顶互逆，直接走向父亲。
• 否则走向对应的儿子。这个儿子不存在就创建，已经存在就复用。

弹栈后重新压入同一个字符，要回到原来的儿子。 不能每次压栈都创建新节点，否则两次相同的栈会得到不同编号，合法区间就漏掉了。

一个非空栈由去掉栈顶后的内容和栈顶字符唯一确定，因此这样的编号与栈内容一一对应，不需要哈希，也没有碰撞问题。

每个状态留下最有用的一个转移

令当前前缀的节点编号为 $state_i$，对每个节点保存

$$best[u]=\max_{j<i,\ state_j=u}(f_j-W_j).$$

处理到第 $i$ 位，先更新栈状态和收益前缀和，再计算

$$f_i=\max(f_{i-1},W_i+best[state_i]).$$

随后用 $f_i-W_i$ 更新 $best[state_i]$，供后面的右端点使用。初始 $f_0=W_0=0$，空栈节点的 $best$ 为 $0$，其他节点为负无穷。

这里按状态取最大值，恰好枚举了前面证明过的全部合法左端点。$f_{i-1}$ 则保留了不选当前位置的方案，两者一起覆盖所有选择。全负收益时，始终不选，答案就是 $0$。

每个字符最多创建一个节点，总节点数不超过 $n+1$。状态树的跳转和 DP 更新都是常数时间，所以总时间、空间均为 $O(n)$。收益前缀和与 DP 值可能达到 $2\times10^{14}$，必须用 long long。

不会完整做法时，可以停在哪一步

$n\le2000$ 的 18 分可以直接枚举区间，固定左端点后不断向右扩展，用栈判断能否消空。栈空就用这个区间做一次前缀 DP 转移，时间 $O(n^2)$。

不一定要把所有合法区间存下来。把 $f$ 初始化为 $0$，按左端点 $l$ 递增枚举。当 $l>1$ 时，先把 $f_{l-2}$ 传播到 $f_{l-1}$。此时所有结束在 $l-1$ 或更早位置的片段都已经处理，$f_{l-1}$ 已经确定，便可以用它更新每个合法的 $f_r$。最后再把 $f_{n-1}$ 传播到 $f_n$，空间只需 $O(n)$。

只含 a/A 的 18 分就是开头的前缀差做法，差值在 $[-n,n]$ 内，用数组维护对应的 $best$，时间、空间均为 $O(n)$。

栈深不超过 $20$ 的 14 分，可以完整编码这个短栈。四个字符编码为 $0,1,2,3$，用 $h=1$ 表示空栈；压入 $c$ 时令 $h=4h+c$，弹栈时令 $h=\lfloor h/4\rfloor$。最高位的 $1$ 用来区分不同长度和前导零，最多只占 41 位。用 map 按这个精确编码维护 $best$，时间 $O(n\log n)$、空间 $O(n)$。

这三种方法组合可以保证 50 分。它们分别保留了枚举区间、用一个整数表示状态、用短串表示状态的做法；完整解法再把任意长度的状态交给树节点表示。

参考代码

#include <algorithm>
#include <array>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    string s;
    cin >> n >> s;
    vector<array<int, 4>> child(n + 1, array<int, 4>{});
    vector<int> parent(n + 1), top(n + 1, -1);
    const ll NEG = LLONG_MIN / 4;
    vector<ll> best(n + 1, NEG);
    best[0] = 0;
    int states = 0, state = 0;
    ll prefix = 0, answer = 0;
    auto code = [](char c) {
        if (c == 'a') return 0;
        if (c == 'A') return 1;
        if (c == 'b') return 2;
        return 3;
    };
    for (int i = 0; i < n; ++i) {
        ll w;
        cin >> w;
        int c = code(s[i]);
        if (state && (top[state] ^ 1) == c) {
            state = parent[state];
        } else {
            // Cache each exact (parent state, last symbol) once.
            if (!child[state][c]) {
                int id = ++states;
                child[state][c] = id;
                parent[id] = state;
                top[id] = c;
            }
            state = child[state][c];
        }
        prefix += w;
        if (best[state] != NEG) answer = max(answer, prefix + best[state]);
        best[state] = max(best[state], answer - prefix);
    }
    cout << answer << '\n';
}