字符串“可消除的”，考虑类似于括号匹配的办法： 维护一个栈，按顺序遍历字符串，若当前字符恰好等于栈顶，则弹出栈顶；反之则将该字符入栈。若遍历结束后，栈为空，则说明该字符串是“可消除的“。 求解输入字符串的所有非空连续子串中，有多少个是可消除的。 暴力枚举所有子串，采用上述方法判断。枚举子串，可以通过枚举长度、枚举起点，然后遍历子串进行判断，时间复杂度 O(n^3) 。哈，过了一半。 注意到对于起点相同的子串，只要遍历过程中栈为空，那么就说明从起点到当前为止是个“可消除的”的字符串。所以从某个起点开始，只需要遍历一次起点到最后，维护一个栈来解决即可，具体地：遍历字符串的每一个字符下标，作为子串的起点，每次维护一个栈，遍历从起点到最后的所有字符，做一遍括号匹配，同时记录过程中栈被弹为空的次数即可。时间复杂度 O(n^2)。哎呦，过了。 这个题目是 [CSP-S 2023] T2 消消乐，S组题不可能这么简单让拿满分的。时间优化-考虑DP 可消除串等价于合法括号序列的变种： 两个相同字符配对消除（类似 ()） 若 [l, m] 和 [m+1, r] 都可消除，则 [l, r] 也可消除（拼接性） 状态定义 f[i]：以 i 结尾的可消除子串个数 g[i]：以 i 结尾的最短可消除子串的左端点（不存在则为 0） 最后对所有f[i]（1<=i<=n）求和。