链接
https://codeforces.com/contest/149/problem/D
题意
给定一个字符串 $s$，是一个合法的括号序列。我们打算对这个括号序列进行染色，有以下要求：
- 每个字符有三种情况：不染色，染成红色，染成蓝色。
- 每对匹配的括号，有且仅有一个字符被染色。
- 所有相邻的两个字符，不能染成同一种颜色。
求满足要求的括号序列染色方案数，答案可能很大，输出答案对 $1e9 + 7$ 取模的结果。
思路
区间 DP。
因为 $s$ 是一个合法的括号序列，所以每个 ( 都有一个对应的 )。
若 $s_i$ 为 (，将与其对应的 ) 记为 $nxt_i$，定义 $dp_{l,r,cl,cr}$ 为区间左端 $l$ 颜色为 $cl$ 右端 $r$ 颜色为 $cr$ 的方案数，考虑如下情况：
- 当 $nxt_l=r$ 时，$dp_{l,r,cl,cr}=\sum dp_{l+1,r-1,cl^{‘},cr^{‘}}$；
- 当 $nxt_l\neq r$ 时，$dp_{l,r,cl,cr}=\sum dp_{l,nxt_l,cl,cr^{‘}} \times dp_{nxt_l+1,r,cl^{‘},cr}$；
- 当 $l+1=r$ 时，$dp_{l,r,cl,cr}=1$。
当左右端颜色符合要求才能转移，记忆化搜索求解。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| #include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
const LL MOD=1e9+7;
const int N=705;
int nxt[N],stk[N],top;
LL dp[N][N][3][3];
LL dfs(int l,int r,int cl,int cr) {
if(dp[l][r][cl][cr]!=-1) return dp[l][r][cl][cr];
dp[l][r][cl][cr]=0;
if(l+1==r) {
if(cl==cr||cl+cr==3) return 0;
return dp[l][r][cl][cr]=1;
}
if(nxt[l]==r) {
if(cl==cr||cl+cr==3) return 0;
for(int i=0;i<3;i++) {
for(int j=0;j<3;j++) {
if(cl&&i&&cl==i||j&&cr&&j==cr) continue;
dp[l][r][cl][cr]=(dp[l][r][cl][cr]+dfs(l+1,r-1,i,j))%MOD;
}
}
return dp[l][r][cl][cr];
}
dp[l][r][cl][cr]=0;
for(int i=0;i<3;i++) {
for(int j=0;j<3;j++) {
if(i&&j&&i==j) continue;
dp[l][r][cl][cr]=(dp[l][r][cl][cr]+dfs(l,nxt[l],cl,i)*dfs(nxt[l]+1,r,j,cr))%MOD;
}
}
return dp[l][r][cl][cr];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;cin>>s;
int n=SZ(s);
for(int i=n-1;~i;i--) {
if(s[i]==')') stk[++top]=i;
else nxt[i]=stk[top--];
}
memset(dp,-1,sizeof dp);
LL res=0;
for(int i=0;i<3;i++) {
for(int j=0;j<3;j++) {
res=(res+dfs(0,n-1,i,j))%MOD;
}
}
cout<<res<<'\n';
return 0;
}
|