暴力->通过->时间优化

字符串“可消除的”，考虑类似于括号匹配的办法：
维护一个栈，按顺序遍历字符串，若当前字符恰好等于栈顶，则弹出栈顶；反之则将该字符入栈。若遍历结束后，栈为空，则说明该字符串是“可消除的“。
求解输入字符串的所有非空连续子串中，有多少个是可消除的。

暴力枚举所有子串，采用上述方法判断。枚举子串，可以通过枚举长度、枚举起点，然后遍历子串进行判断，时间复杂度 O(n^3) 。哈，过了一半。

#include<bits/stdc++.h>
using namespace std;
int main() {
	int n, ans=0;
	string s;
	cin>>n>>s;
	int len=s.size();
	for(int l=1; l<=len; l++){
		for(int i=0; i+l<=len; i++){
			int j=l-1+i;
			stack<char> st;
			for(int k=i; k<=j; k++){
				if(!st.empty() && st.top()==s[k]){
					st.pop();
				}else st.push(s[k]);
			}
			if(st.empty()) ans++;
		}
	}
	cout<<ans;
	return 0;
}

注意到对于起点相同的子串，只要遍历过程中栈为空，那么就说明从起点到当前为止是个“可消除的”的字符串。所以从某个起点开始，只需要遍历一次起点到最后，维护一个栈来解决即可，具体地：遍历字符串的每一个字符下标，作为子串的起点，每次维护一个栈，遍历从起点到最后的所有字符，做一遍括号匹配，同时记录过程中栈被弹为空的次数即可。时间复杂度 O(n^2)。哎呦，过了。

#include<bits/stdc++.h>
using namespace std;
int main() {
	int n, ans=0;
	string s;
	cin>>n>>s;
	int len=s.size();
	for(int i=0; i<len; i++) {
		stack<char> st;
		for(int j=i; j<len; j++) {
			if(!st.empty() && st.top()==s[j]) {
				st.pop();
				if(st.empty()) ans++;
			} else st.push(s[j]);
		}
	}
	cout<<ans;
	return 0;
}

这个题目是 [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）求和。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e6+10;
int dp[N]; // dp[i]：以i结尾的可消除子串数
int last[N]; //last[i]：以i结尾的最短可消除串左端点
long long ans;
int main() {
	int n;
	string s;
	
	cin>>n>>s; s='%'+s;
	for(int i=1; i<=n; i++) {
		for(int j=i-1; j>0; j=last[j]-1) {
			if(s[i]==s[j]) {
				last[i]=j;
				break;
			}
		}
		if(last[i]) {
			dp[i]=dp[last[i]-1]+1;
			ans+=dp[i];
		}
	}
	cout<<ans<<endl;
	return 0;
}