Coloring Brackets CF-149D（区间DP）
题意：
给定合法括号序列，可以给括号涂三种颜色：红色，蓝色，不上色。涂色需要满足以下两个要求：
①匹配括号必须一个上色一个不上色。
②相邻括号不能上同一种颜色，但可以同时不上色。
求上色方案数。
思路：
$dp[i][j][k][l]$表示区间$(i,j)$中$i$上颜色$k$，$j$上颜色$l$的方案数。分三种情况：
①$i$和$j$相邻，则可以保证$i$和$j$匹配，那么$dp[i][j][0][1]=dp[i][j][0][2]=dp[i][j][1][0]=dp[i][j][2][0]=1$。
②$i$和$j$匹配，递归求得$dp[i+1][j-1][k][l]$的相应的方案数，转移得到：
$dp[i][j][0][1] += dp[i + 1][j - 1][k][0] + dp[i + 1][j - 1][k][2]$
$dp[i][j][0][2] += dp[i + 1][j - 1][k][0] + dp[i + 1][j - 1][k][1]$
$dp[i][j][1][0] += dp[i + 1][j - 1][0][k] + dp[i + 1][j - 1][2][k]$
$dp[i][j][2][0] += dp[i + 1][j - 1][0][k] + dp[i + 1][j - 1][1][k]$
③$i$和$j$不匹配，那么找到i的匹配点，将$(i,j)$区间拆分成$(i,mat[i])$和$(mat[i]+1,j)$，可以保证，每个区间内可以找到自己的匹配，不存在交叉匹配。
$dp[i][j][k][l]=dp[i][mat[i]][k][u]*dp[mat[i]+1][j][o][l]$
代码：
1 //#include<bits/stdc++.h> 2 #include <set> 3 #include <map> 4 #include <stack> 5 #include <cmath> 6 #include <queue> 7 #include <cstdio> 8 #include <string> 9 #include <vector> 10 #include <cstring> 11 #include <iostream> 12 #include <algorithm> 13 14 #define ll long long 15 #define pll pair<ll,ll> 16 #define pii pair<int,int> 17 #define bug printf("********* ") 18 #define FIN freopen("input.txt","r",stdin); 19 #define FON freopen("output.txt","w+",stdout); 20 #define IO ios::sync_with_stdio(false),cin.tie(0) 21 #define ls root<<1 22 #define rs root<<1|1 23 #define Q(a) cout<<a<<endl 24 25 using namespace std; 26 const int inf = 2e9 + 7; 27 const ll Inf = 1e18 + 7; 28 const int maxn = 700 + 5; 29 const int mod = 1e9 + 7; 30 31 char s[maxn]; 32 int mat[maxn]; 33 ll dp[maxn][maxn][5][5]; 34 stack<int>sta; 35 36 void DP(int i, int j) 37 { 38 if (i + 1 == j)//最小括号 39 { 40 for (int k = 1; k <= 2; ++k) dp[i][j][k][0] = dp[i][j][0][k] = 1; 41 return; 42 } 43 if (mat[i] == j)//匹配的括号 44 { 45 DP(i + 1, j - 1); 46 for (int k = 0; k <= 2; ++k) 47 { 48 dp[i][j][0][1] += dp[i + 1][j - 1][k][0] + dp[i + 1][j - 1][k][2]; 49 dp[i][j][0][2] += dp[i + 1][j - 1][k][0] + dp[i + 1][j - 1][k][1]; 50 dp[i][j][1][0] += dp[i + 1][j - 1][0][k] + dp[i + 1][j - 1][2][k]; 51 dp[i][j][2][0] += dp[i + 1][j - 1][0][k] + dp[i + 1][j - 1][1][k]; 52 } 53 dp[i][j][0][1] %= mod; 54 dp[i][j][0][2] %= mod; 55 dp[i][j][1][0] %= mod; 56 dp[i][j][2][0] %= mod; 57 return; 58 } 59 //划分区间，两个区间不存在交叉匹配 60 DP(i, mat[i]); 61 DP(mat[i] + 1, j); 62 for (int k = 0; k <= 2; ++k) 63 for (int l = 0; l <= 2; ++l) 64 for (int u = 0; u <= 2; ++u) 65 for (int o = 0; o <= 2; ++o) 66 { 67 if (l == u && l != 0) continue; 68 dp[i][j][k][o] += dp[i][mat[i]][k][l] * dp[mat[i] + 1][j][u][o]; 69 dp[i][j][k][o] %= mod; 70 } 71 } 72 73 int main() 74 { 75 memset(dp, 0, sizeof dp); 76 scanf("%s", s); 77 int len = strlen(s); 78 for (int i = 0; i < len; ++i)//配对 79 { 80 if (s[i] == '(') sta.push(i); 81 if (s[i] == ')') 82 { 83 mat[i] = sta.top(); 84 mat[sta.top()] = i; 85 sta.pop(); 86 } 87 } 88 DP(0, len-1); 89 ll ans = 0; 90 for(int i=0;i<=2;++i) 91 for (int j = 0; j <= 2; ++j) 92 { 93 ans += dp[0][len - 1][i][j]; 94 ans %= mod; 95 } 96 printf("%lld ", ans); 97 }