CF149D Coloring Brackets 题解

题目链接：CF149D Coloring Brackets

题意：给出一个配对的括号序列（如 “ (())() texttt{(())()} (())()”、“ () texttt{()} ()” 等，“ )() texttt{)()} )()”、“ (() texttt{(()} (()”是不符合要求的），对该序列按照以下方法染色。

一个括号可以染成红色、蓝色或者不染色。
一对匹配的括号需要且只能将其中一个染色。
相邻两个括号颜色不能相同（但都可以不染色）。

求符合条件的染色方案数，对 1000000007 1000000007 1000000007 取模。

容易发现这个题目就是个区间dp

但是仅仅用 d p [ l ] [ r ] dp[l][r] dp[l][r] 并不能表示出两侧括号的颜色

因此设 d p [ l ] [ r ] [ i ] [ j ] dp[l][r][i][j] dp[l][r][i][j] 为区间 [ l , r ] [l,r] [l,r] 内且左右两侧的颜色分别为 i , j i,j i,j 时的方案数（0为不染色，1为红，2为蓝）

考虑边界：当 l + 1 = r l+1=r l+1=r 时，有
() text{()} ()

dp[l][r][0][1]=dp[l][r][0][2]=dp[l][r][1][0]=dp[l][r][2][0]=1;

一般地，

当 l l l 与 r r r 配对时，有
( … ) text{(}dotstext{)} (…)

for(int i=0; i<=2; i++)
    for(int j=0; j<=2; j++)
    {
        if(j!=1) dp[l][r][0][1]=(dp[l][r][0][1]+dp[l+1][r-1][i][j])%mod;
        if(j!=2) dp[l][r][0][2]=(dp[l][r][0][2]+dp[l+1][r-1][i][j])%mod;
        if(i!=1) dp[l][r][1][0]=(dp[l][r][1][0]+dp[l+1][r-1][i][j])%mod;
        if(i!=2) dp[l][r][2][0]=(dp[l][r][2][0]+dp[l+1][r-1][i][j])%mod;
    }

当 l l l 与 r r r 不配对时，有
( … ) … ( … ) text{(}dotstext{)}dotstext{(}dotstext{)} (…)…(…)
以及
( … )( … ) text{(}dotstext{)}text{(}dotstext{)} (…)(…)
等情况，不过本质上是一样的

for(int i=0; i<=2; i++)
    for(int j=0; j<=2; j++)
        for(int p=0; p<=2; p++)
            for(int q=0; q<=2; q++)
            {
                if(j==1&&p==1||j==2&&p==2)continue;
                dp[l][r][i][q]=(dp[l][r][i][q]+dp[l][mch[l]][i][j]*dp[mch[l]+1][r][p][q]%mod)%mod;
            }

值得注意的是，本题并不适用一般的dp顺序，而是采用记忆化搜索

因为本题要求配对的括号有且仅有一个被染色，而一般的顺序难以保证配对的括号在同一个区间内，即不能保证转移中用到的序列都是合法的，因此较为麻烦

代码：

#include 
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(705)
const int mod=1e9+7;
char a[N];
int n,mch[N],stk[N],top,dp[N][N][3][3];
void dfs(int l,int r)
{
    if(l+1==r)dp[l][r][0][1]=dp[l][r][0][2]=dp[l][r][1][0]=dp[l][r][2][0]=1;
    else if(mch[l]==r)
    {
        dfs(l+1,r-1);
        for(int i=0; i<=2; i++)
            for(int j=0; j<=2; j++)
            {
                if(j!=1) dp[l][r][0][1]=(dp[l][r][0][1]+dp[l+1][r-1][i][j])%mod;
		        if(j!=2) dp[l][r][0][2]=(dp[l][r][0][2]+dp[l+1][r-1][i][j])%mod;
		        if(i!=1) dp[l][r][1][0]=(dp[l][r][1][0]+dp[l+1][r-1][i][j])%mod;
		        if(i!=2) dp[l][r][2][0]=(dp[l][r][2][0]+dp[l+1][r-1][i][j])%mod;
            }
    }else
    {
        dfs(l,mch[l]);dfs(mch[l]+1,r);
        for(int i=0; i<=2; i++)
            for(int j=0; j<=2; j++)
                for(int p=0; p<=2; p++)
                    for(int q=0; q<=2; q++)
                    {
                        if(j==1&&p==1||j==2&&p==2)continue;
                        dp[l][r][i][q]=(dp[l][r][i][q]+dp[l][mch[l]][i][j]*dp[mch[l]+1][r][p][q]%mod)%mod;
                    }
                        
    }
}
signed main()
{
    scanf("%s",(a+1));
    n=strlen(a+1);
    for(int i=1; i<=n; i++)
    {
        if(a[i]=='(')stk[++top]=i;
        else mch[stk[top]]=i,mch[i]=stk[top],--top;
    }
    dfs(1,n);
    int ans=0;
    for(int i=0; i<=2; i++)
        for(int j=0; j<=2; j++)
            ans=(ans+dp[1][n][i][j])%mod;
    printf("%lldn",ans);
    return 0;
}

本文很多地方参考了这篇文章，写的非常好 ✅ ✅ ✅

转载请说明出处

CF149D Coloring Brackets 题解

C/C++/C#相关栏目本月热门文章