Codeforces 149 D. Coloring Brackets

問題

対応の取れた括弧からなる文字列が与えられる。
この文字列のそれぞれの文字について、

• 色を塗らない
• 赤色に塗る
• 青色に塗る

のどれかをする。

対応する括弧は、どちらか一方のみが色を塗られていて、、
かつ、隣り合うどの文字も同じ色に塗られていないような色の塗り方は何通りあるか、
mod 10^9+7で求めよ。

制約条件

文字列の長さ≦700

方針

動的計画法による。
dp[l][r][左側で禁止される色][右側で禁止される色]を、
[l,r)の範囲に、禁止される色が上のような条件で色を塗る塗り方の場合の数とする。

これをメモ化再帰すればよい。
最初に括弧の対応を求めておく必要がある。
これは、(がきたらその位置をスタックに積み、)が来たらスタックの一番上の値が対応する括弧になっているのでそれでやる。

ソースコード

const int mod=(int)1e9+7;
int dp[701][701][3][3];
string in;
int n, p[701];

int rec(int l,int r,int fl,int fr){
	int &res=dp[l][r][fl][fr];
	if(res>=0)return res;
	if(l>=r)return res=1;
	
	res=0;
	rep(cl,3)rep(cr,3){
		if(cl>0&&cr>0||cl==0&&cr==0)continue;
		if(fl>0&&cl==fl)continue;
		if(p[l]==r-1&&fr>0&&cr==fr)continue;
		(res+=(ll)rec(l+1,p[l],cl,cr)*rec(p[l]+1,r,cr,fr)%mod)%=mod;
	}
	return res;
}
void run()
{
	cin>>in;
	n=in.size();
	stack<int> st;
	rep(i,n){
		if(in[i]=='('){
			st.push(i);
		}
		else{
			p[st.top()]=i;
			p[i]=st.top();
			st.pop();
		}
	}
	memset(dp,-1,sizeof(dp));
	cout<<rec(0,n,0,0)<<endl;
}