P9753 [CSP-S 2023] 消消乐
无钩七不改名
·
·
生活·游记
$n^2$ 是枚举每个左/右端点，用栈判断是否可以消除。
正解还是个 dp。
可以发现，每个可删区间一定是一个最小可删区间（指不能由两个可删区间组成）或者多个最小可删区间首尾相接。
设 $pre_i$ 表示以 $i$ 为右端点且能构成可删区间的区间中，最右的左端点的位置，$dp_i$ 表示以 $i$ 为右端点的可删区间一共有多少个。
显而易见，$dp_i=dp_{pre_i-1}+1$。
那么问题就转化为怎么求 $pre_i$。
两种情况，如果 $c_i=c_{i-1}$，那么显然 $pre_i=i-1$。否则考虑到 $c_i=c_{pre_i}$，我们可以从 $j=i-1$ 开始不断往前跳，如果 $pre_j$ 不存在，跳出，否则看看 $c_i$ 是否与 $c_{pre_j-1}$ 相同。如果相同，$pre_i=pre_j-1$，跳出。如果不同，令 $j=pre_j-1$，继续跳。
时间复杂度我不会证，但是显然正确吧（？）。
### 赛后补题代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=2000005;
int n;
char c[N];
int pre[N],dp[N];
long long ans;
int read(){
int f=1,k=0;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
k=k*10+ch-'0';
ch=getchar();
}
return f*k;
}
int main(){
n=read();
scanf(" %s",c+1);
for(int i(2);i<=n;++i){
if(c[i]==c[i-1]){
pre[i]=i-1;
continue;
}
int j=i-1;
while(pre[j]){
if(c[i]==c[pre[j]-1]){
pre[i]=pre[j]-1;
break;
}
j=pre[j]-1;
}
}
for(int i(2);i<=n;++i)
if(pre[i]){
dp[i]=dp[pre[i]-1]+1;
ans+=dp[i];
}
printf("%lld",ans);
return 0;
}
```