[CSP-S 2023] 消消乐

题目传送门

[CSP-S 2023] 消消乐

思路

考虑 DP。

显然，设 \(f_i\) 表示以位置 \(i\) 结尾的可消除序列的个数，我们对每一个可消除序列考虑模型，大概就是这个样子：\(\text{a}\cdots\text{ab}\cdots\text{b}\)。

那么我们当前位置为 \(i\)，前一个可以与 \(i\) 匹配的最大的下标为 \(low_i\)，显然：

到这里其实都很简单的，去年的我考场上也是想到这里就戛然而止，最后写了一个 50pts 的暴力遗憾离场。

但我们可以考虑一个一个往前找，就是那个 \(O(n^2)\) 的暴力做法，考虑优化。

假设当前位置为 \(i\)，\(low_{1\rightarrow i}\) 已经求出，那么我们注意到类似于 \(\text{a}\cdots\text{a}\) 的子串中的省略号一定是由若干个可消除字串。那么我们可以一个一个往前跳。

由于最多只有 \(26\) 个字母，所以每一次向前跳的期望应该是一个常数级别，所以时间复杂度是线性的。

代码

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

string s;
int f[2000005]={0},n,ans=0;
int last[2000005]={0};

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	
	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]!=0)
			f[i]+=(1ll+f[last[i]-1]);
	}
	
	for(int i=1;i<=n;i++)
		ans+=f[i];
		
	cout<<ans<<endl;
	
	return 0;
}