题目链接：Coloring Brackets
题目大意: 给一个给定括号序列，给该括号上色，上色有三个要求 1、只有三种上色方案，不上色，上红色，上蓝色 2、每对括号必须只能给其中的一个上色 3、相邻的两个不能上同色 求0~len-1这一区间内有多少种上色方案 分析： dp[l][r][i][j]表示l-r区间两端颜色分别是i,j的方案数 0代表不上色，1代表上红色，2代表上蓝色 初始化 ： if (l+1==r) dp[l][r][0][1] = dp[l][r][0][2] = 1; dp[l][r][1][0] = dp[l][r][2][0] = 1; 状态转移： 1.若 l 和 r 处于匹配位置 dp[l][r][0][1] += dp[l+1][r-1][i][j] 其中为了使r和r-1（相邻）不同色 j != 1 其他dp[l][r][i][j]同理 2.若 l 和 r 不匹配 那么找到和 l 相匹配的位置 p 将区间[l,r]分成区间[l,p] ∪[p+1,r] 这样的方案数将是两区间的乘积 即dp[l][p]*dp[p+1][r] 乘的时候注意限制条件即可
#define mem(a,x) memset(a,x,sizeof(a)) #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<set> #include<stack> #include<cmath> #include<map> #include<stdlib.h> #include<cctype> #include<string> #define Sint(n) scanf("%d",&n) #define Sll(n) scanf("%I64d",&n) #define Schar(n) scanf("%c",&n) #define Sint2(x,y) scanf("%d %d",&x,&y) #define Sll2(x,y) scanf("%I64d %I64d",&x,&y) #define Pint(x) printf("%d",x) #define Pllc(x,c) printf("%I64d%c",x,c) #define Pintc(x,c) printf("%d%c",x,c) using namespace std; typedef long long ll; /* 题目大意: 给一个给定括号序列，给该括号上色，上色有三个要求 1、只有三种上色方案，不上色，上红色，上蓝色 2、每对括号必须只能给其中的一个上色 3、相邻的两个不能上同色 求0~len-1这一区间内有多少种上色方案 分析： dp[l][r][i][j]表示l-r区间两端颜色分别是i,j的方案数 0代表不上色，1代表上红色，2代表上蓝色 初始化 ： if (l+1==r) dp[l][r][0][1] = dp[l][r][0][2] = 1; dp[l][r][1][0] = dp[l][r][2][0] = 1; 状态转移： 1.若 l 和 r 处于匹配位置 dp[l][r][0][1] += dp[l+1][r-1][i][j] 其中为了使r和r-1（相邻）不同色 j != 1 其他dp[l][r][i][j]同理 2.若 l 和 r 不匹配 那么找到和 l 相匹配的位置 p 将区间[l,r]分成区间[l,p] ∪[p+1,r] 这样的方案数将是两区间的乘积 即dp[l][p]*dp[p+1][r] 乘的时候注意限制条件即可 */ const int N = 707; const int mod = 1e9+7; int match[N];//match[i] = j表示i和j是匹配的 struct Node { ll s[3][3]; void init() { mem(s,0); } void MOD() { for (int i = 0;i < 3;++i) { for (int j = 0;j < 3;++j) { s[i][j] %= mod; } } } }dp[N][N]; char s[N]; bool isleft(char ch) { return ch == '('; } void Match()//预处理匹配情况 { stack<int>q;//平衡符号用栈匹配 int n = strlen(s)-1; for (int i = 0;i <= n;++i) { if (isleft(s[i])) q.push(i); else { int j = q.top(); q.pop(); match[i] = j; match[j] = i; } } } Node DP(int l,int r) { if (l >= r) { Node tmp;tmp.init(); return tmp; } if (~dp[l][r].s[0][0]) return dp[l][r]; Node &mum = dp[l][r]; mum.init(); if (l + 1 == r) { mum.s[0][1] = mum.s[0][2] = 1; mum.s[1][0] = mum.s[2][0] = 1; return mum; } if (match[l] == r)//若匹配 { Node son = DP(l+1,r-1);//子区间 for (int i = 0;i < 3;++i) { for (int j = 0;j < 3;++j) { if (j!=1) mum.s[0][1] += son.s[i][j]; if (j!=2) mum.s[0][2] += son.s[i][j]; if (i!=1) mum.s[1][0] += son.s[i][j]; if (i!=2) mum.s[2][0] += son.s[i][j]; mum.MOD(); } } } else //若不匹配 { int p = match[l];//找到与l匹配的区间将[l,r]一分为二 Node ls = DP(l,p);//左区间 Node rs = DP(p+1,r);//右区间 for (int i = 0;i < 3;++i) { for (int j = 0;j < 3;++j) { for (int k = 0;k < 3;++k) { for (int l = 0;l < 3;++l) { if (k==1&&l==1) continue;//相邻同色 if (k==2&&l==2) continue; mum.s[i][j] += (ls.s[i][k]*rs.s[l][j])%mod; mum.s[i][j]%=mod; } } } } } return mum; } int main() { while (~scanf("%s",s)) { Match();mem(dp,-1); int n = strlen(s)-1; ll ans = 0; for (int i = 0;i < 3;++i) { for (int j = 0;j < 3;++j) { ans += DP(0,n).s[i][j]; ans %= mod; } } Pllc(ans,'\n'); } return 0; }