Coloring Brackets CodeForces - 149D
区间DP
题目描述：输入一串保证合法的括号序列，要求给这个括号序列串染色，满足三个要求：（1·）染色要不为红，要么为蓝，要么不染色（2）每队匹配的括号，只能有一个染色（3）相邻的染色的括号不能染一个颜色。
解题分析：定义dp[l][r][x][y]为左边界为l，染色为x,右边界为r，染色为y满足条件的染色方案数。状态转移方程分两类：第一类是l和r本身是匹配的，另一类是不匹配的，此时就需要找到匹配的字符位置，再进行处理了。转移的过程就是枚举所有的x,y,注意需要判断合不合法，合法的话就转移，具体状态转移方程在代码中。
代码如下：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int color[4][2] = {{0,1},{0,2},{1,0},{2,0}};
const int maxn = 700 + 10;
const LL mod = 1000000007;
LL dp[maxn][maxn][3][3];
int stk[maxn],match[maxn];
char str[maxn];
int n;
LL dfs(int l,int r,int x,int y)
{
if(dp[l][r][x][y] > -1) return dp[l][r][x][y];
if(l == r - 1)//边界处理
{
for(int i = 0; i < 4; i++)
{
if(x == color[i][0] && y == color[i][1]) return dp[l][r][x][y] = 1;//如果是合法的话
}
return dp[l][r][x][y] = 0;//不合法
}
//处理非边界的情况
LL ans = 0;
if(match[l] == r)//如果左右两边界的括号匹配的话
{
bool is_ok = false;
for(int i = 0; i < 4; i++)
{
if(x == color[i][0] && y == color[i][1])//如果合法的话
{
is_ok = true;
for(int j = 0; j < 3; j++)
{
for(int k = 0; k < 3; k++)
{
if(j != 0 && j == x || k != 0 && k == y) continue;//注意相邻染色的括号不能为同一个颜色
ans = (ans + dfs(l + 1,r - 1,j,k)) % mod;
}
}
}
}
if(!is_ok) return dp[l][r][x][y] = 0;//不合法
}
else
{
for(int i = l + 1; i <= r - 1; i++)
{
if(match[l] == i)//寻找与左边界匹配的括号位置
{
for(int j = 0; j < 3; j++)
{
for(int k = 0; k < 3; k++)
{
if(j != 0 && k != 0 && j == k) continue;//不和法的情况
ans = (ans + dfs(l,i,x,j) * dfs(i + 1,r,k,y)) % mod;
}
}
break;
}
}
}
return dp[l][r][x][y] = ans;
}
int main()
{
scanf("%s",str + 1);
n = strlen(str + 1);
int cnt = 0;
for(int i = 1; i <= n; i++)//预处理每个字符与之匹配的字符在那个位置
{
if(str[i] == '(') stk[cnt++] = i;
else
{
int t = stk[--cnt];
match[i] = t;
match[t] = i;
}
}
memset(dp,-1,sizeof(dp));
LL ans = 0;
for(int i = 0; i < 3; i++)
{
for(int j = 0; j < 3; j++)
{
ans = (ans + dfs(1,n,i,j)) % mod;
}
}
printf("%lld\n",ans);
return 0;
}
