评测记录

思路跟大部分题解不同，用的是记忆化搜索。

思路：计算 f[l][r] 时假设 a[l] 是先涂的颜色，然后递归计算涂 $[l,r]$ 这段中被 a[l] 的颜色分隔开的若干个区间的答案。详见代码。

#include<bits/stdc++.h>
using namespace std;
int n,f[55][55];
char a[55];
int dfs(int l,int r){
	if (f[l][r]) return f[l][r];
	int p1=l,p2=l,ans=0;
	for (int i=l;i<=r+1;i++){
		if (a[i]==a[l]||i==r+1){
			if (p1<p2){
				ans+=dfs(p1+1,p2);
			}
			p1=i;
		}
		else p2=i;
	}
	return f[l][r]=ans+1;
}
int main(){
	ios::sync_with_stdio(0);
	cin>>a;
	n=strlen(a);
	cout<<dfs(0,n-1);
	return 0;
}