Photo by eberhard grossgasteiger from Pexels
（区间dp好题！）
题目大意是说，给定一个保证配对的括号序列S，现在要对这些括号染上蓝色或红色，且需要满足以下三个要求:
- 对于每个括号，要么染上红色，要么染上蓝色，要么不染色
- 对于每一对配对的括号，有且仅有一个括号被染色
- 任意两个相邻的括号都没有相同的颜色
问一共有多少种染色方案。
思路是区间DP，用\(dp[lef][rig][l][r]\)表示对于子区间\(S_{lef···rig}\)，在左端括号颜色为\(l\)右端括号颜色为\(r\)的情况下，所能得到的染色方案数。如果\(S_{lef}\)和\(S_{rig}\)配对，则处理\(S_{lef+1···rig-1}\)，然后从\(dp[lef+1][rig-1][i][j]\)转移得到\(dp[lef][rig][1][0]\)，\(dp[lef][rig][2][0]\)，\(dp[lef][rig][0][1]\)，\(dp[lef][rig][0][2]\)。如果不配对，则找出区间\([lef,rig]\)中和左括号配对的那个括号的下标\(mat\)，然后依次为区间断点来合并区间转移得到结果。此时的状态转移方程为 \[ dp[lef][rig][i][j]=(dp[lef][rig][i][j]+dp[lef][mat][i][k]*dp[mat+1][rig][p][j])\ \%\ mod \] 关于如何找到左括号配对的右括号，只需要用个栈做一下预处理即可。左括号入栈，右括号将当前栈顶元素与右括号配对并弹栈。
最后只需要把\(dp[1][len][0...2][0...2]\)分别加起来即可得到答案。
代码如下：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <utility>
#include <map>
#include <stack>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
#define IOS std::ios::sync_with_stdio(false)
const int maxn=1e5+5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
char str[705];
int match[705];
ll dp[705][705][3][3];
const int mod=1e9+7;
void init(int len)
{
stack<int> stk;
for(int i=1;i<=len;i++){
if(str[i]=='('){
stk.push(i);
}else{
match[i]=stk.top();
match[stk.top()]=i;
stk.pop();
}
}
}
void solve(int lef,int rig)
{
// mst(dp,0);
if(rig-1==lef){
dp[lef][rig][1][0]=dp[lef][rig][0][1]=dp[lef][rig][2][0]=dp[lef][rig][0][2]=1;
return ;
}
if(match[lef]==rig){
solve(lef+1,rig-1);
for(int i=0;i<3;i++){ //枚举左端颜色
for(int j=0;j<3;j++){ //枚举右端颜色
if(i!=1)
dp[lef][rig][1][0]=(dp[lef][rig][1][0]+dp[lef+1][rig-1][i][j])%mod;
if(i!=2)
dp[lef][rig][2][0]=(dp[lef][rig][2][0]+dp[lef+1][rig-1][i][j])%mod;
if(j!=1)
dp[lef][rig][0][1]=(dp[lef][rig][0][1]+dp[lef+1][rig-1][i][j])%mod;
if(j!=2)
dp[lef][rig][0][2]=(dp[lef][rig][0][2]+dp[lef+1][rig-1][i][j])%mod;
}
}
}else{
int mat=match[lef];
solve(lef,mat);solve(mat+1,rig);
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
//枚举颜色
for(int k=0;k<3;k++){
for(int p=0;p<3;p++){
//枚举颜色
if(k!=p||k==0){ //<-
dp[lef][rig][i][j]=(dp[lef][rig][i][j]+dp[lef][mat][i][k]*dp[mat+1][rig][p][j])%mod;
}
}
}
}
}
}
}
int main()
{
scanf("%s",str+1);
int len=strlen(str+1);
init(len);
mst(dp,0);
ll ans=0;
solve(1,len);
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
ans=(ans+dp[1][len][i][j])%mod;
printf("%lld\n",ans);
return 0;
}