题解 Coloring Brackets

题目链接

对于括号问题，考虑区间 \(dp\)。这道题的括号序列是固定的，所以直接找出每个括号对应的括号在进行转化即可。

设 \(f_{l,r,0/1/2,0/1/2}\) 表示 \(l\sim r\)，左括号不染色/染红色/染蓝色，右括号不染色/染红色/染蓝色的方案数。

若 \(l,r\) 是一对匹配括号，那么f_{l,r} 便可以由 \(f_{l+1,r-1}\) 转移得来，注意相邻括号颜色不同。

接着进行中间的拆分，注意括号问题不能直接枚举断点 \(k\) 拆分，这样会将 \(()()()\) 分别拆成 \((),()()\) 和 \(()(),()\) 计算两次。所以强行规定第一个拆分的一定是左右括号匹配好的，后面一段不管，也就是将 \([l,r]\) 拆成 \([l,match_l]\) 和 \(match_l+1,r\) 两个区间进行计算，同样注意相邻括号颜色不能相同。

由于很大程度根据括号匹配情况进行 \(dp\)，所以这里采取记忆话搜索进行 \(dp\)。

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

typedef long long LL;
#define PII pair<int,int>
LL read() {
	LL sum=0,flag=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') flag=-1; c=getchar();}
	while(c>='0'&&c<='9') {sum=sum*10+c-'0'; c=getchar();}
	return sum*flag;
}

const int N=710;
const LL MOD=1e9+7;
int n; string s;
int match[N];
LL f[N][N][3][3];

int pd(int l,int r) {
	if(s[l]=='('&&s[r]==')') return 1;
	else return 0;
}

LL dfs(int l,int r,int p1,int p2) {
	if(l>r) return 0;
	if((r-l+1)%2!=0) return 0;
	if(f[l][r][p1][p2]!=-1) return f[l][r][p1][p2];
	f[l][r][p1][p2]=0;
	if(match[l]==r) {
		if((p1&&!p2)||(!p1&&p2)) {
			for(int x1=0;x1<=2;x1++) {
				for(int x2=0;x2<=2;x2++){
					if((p1==x1&&x1)||(p2==x2&&x2)) continue;
					f[l][r][p1][p2]=(f[l][r][p1][p2]+dfs(l+1,r-1,x1,x2))%MOD;
				}
			}			
		}
	}
	for(int x1=0;x1<=2;x1++) {
		for(int x2=0;x2<=2;x2++){
			if(x1==x2&&x1) continue;
			f[l][r][p1][p2]=(f[l][r][p1][p2]+dfs(l,match[l],p1,x1)*dfs(match[l]+1,r,x2,p2))%MOD;
		}
	}
	
	return f[l][r][p1][p2];
}

int main() {
	cin>>s;
	n=s.size(); s=" "+s;
	stack<int> st;
	memset(f,-1,sizeof(f));
	for(int i=1;i<=n;i++) {
		if(st.size()&&s[st.top()]=='('&&s[i]==')') {
			match[st.top()]=i; match[i]=st.top(); st.pop();
		}
		else st.push(i);
	}
	for(int i=1;i<=n-1;i++) {
		if(pd(i,i+1)) {
			f[i][i+1][0][1]=f[i][i+1][0][2]=f[i][i+1][1][0]=f[i][i+1][2][0]=1;
		}
	}
	LL ans=0;
	for(int i=0;i<=2;i++) {
		for(int j=0;j<=2;j++) {
			ans=(ans+dfs(1,n,i,j))%MOD;
		}
	}
	cout<<ans<<endl;


	return 0;
}