Coloring Brackets | 区间计数dp、多条件限制

题目链接：https://codeforces.com/contest/149/problem/D

题目大意：

给出一个合法的括号序列，下面你会给这个括号序列涂色，涂色时要满足下面三个条件：

1.每对匹配的括号必须有且只有一个被染色

2.相邻括号间染色不可以相同

3.每个括号染色的状态只能是 染红，染蓝，不染

询问合法的染色方案数

题目思路：

确实是一个好题

括号匹配必然和区间有关系

考虑区间dp[l][r]

dp[l][r]代表区间[l,r]的合法染色方案数 

但是无法处理相邻颜色是否相同的情况，所以肯定要新增一维:

dp[l][r][x][y]代表区间[l,r]左端点染色[x]，右端点染色[y]的合法染色方案数

那么由于有括号匹配

• 如果当前l 与 r匹配，那么肯定只有4种方案，01、02、10、20，那么就直接可以用[l+1,r-1]的合法方案数考虑合法转移
• 如果当前l 与 r不匹配，那么看一下l的匹配位置在哪，假设匹配位置是pos，那么处理完[l,pos]与[pos+1,r]的方案数之后，便可以根据乘法原理进行合法的转移

好题..

Code:

/*** keep hungry and calm CoolGuang!***/
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define d(x) printf("%lld\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e17;
const ll maxn = 2e5+700;
const int mod= 1e9+7;
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
ll dp[705][705][3][3];
int R[maxn];
int st[maxn];
int dx[4] = {0,0,1,2};
int dy[4] = {1,2,0,0};
char s[maxn];
void dfs(int l,int r){
    if(r-l+1 == 2){///递归方式导致len = 2 只能是单括号匹配
        dp[l][r][0][1] = dp[l][r][0][2] = dp[l][r][2][0] = dp[l][r][1][0] = 1;///匹配
        return ;
    }
    if(R[l] == r){///如果当前匹配
        ///那么两端颜色的选择与[l+1,r-1]有关
        dfs(l+1,r-1);
        for(int i=0;i<3;i++){
            for(int k=0;k<3;k++){
                for(int j=0;j<4;j++){
                    int idx = dx[j],idy = dy[j];
                    if((idx!=0 && idx == i)) continue;
                    if((idy!=0 && idy == k)) continue;
                    dp[l][r][idx][idy] = (dp[l][r][idx][idy] +dp[l+1][r-1][i][k])%mod;
                }
            }
        }
    }
    else{
        int temp = R[l];
        dfs(l,temp);
        dfs(temp+1,r);
        for(int i=0;i<3;i++){
            for(int k=0;k<3;k++){
                for(int x=0;x<3;x++){
                    for(int y=0;y<3;y++){
                        if(k!=0 && k==x) continue;
                        dp[l][r][i][y] = (dp[l][r][i][y] + dp[l][temp][i][k] * dp[temp+1][r][x][y])%mod;
                    }
                }
            }
        }
    }
}
int main(){
    scanf("%s",s+1);
    n = strlen(s+1);
    int top = 0;
    for(int i=1;i<=n;i++){
        if(s[i] == '(') st[++top] = i;
        else R[st[top--]] = i;
    }
    dfs(1,n);
    ll ans = 0;
    for(int i=0;i<3;i++){
        for(int k=0;k<3;k++){
            ans = (ans + dp[1][n][i][k])%mod;
        }
    }
    printf("%lld\n",ans);
    return 0;
}
/***

***/

 

本文地址：https://blog.csdn.net/qq_43857314/article/details/110182932