区间dp [D

区间dp D - Coloring Brackets

题目大意：

给你一个合法的括号字符串，可以给字符串涂颜色，有两个限制

• 每个括号只有三种情况，不上色，上红色，上蓝色
• 每对括号必须只能给其中的一个上色，且必须给一个上色
• 相邻的两个不能上同色，可以都不上色

问有多少种涂色方案？

题解：

注意：这一定是一个合法的括号字符串！！！

(dp[i][j][x][y]) 表示从 (i) 到 (j) 并且将位置 (i) 涂成 (x) 这种颜色，将位置 (j) 涂成 (y) 这种颜色，最多的涂色方案是 (dp[i][j][x][y])

这个不能直接用递推来写，而是用递归写比较好，因为这是一个合法的括号序列，所以每次可以两两括号放进去。

知道转移方程也知道用两两括号放进入递归之后，可以试着自己写一下，应该不太难了。

#include <cstdio>
#include <queue>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <bits/stdc++.h>
#define id first
#define val second
#define inf 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
#define debug(x) printf("debug:%s=%d
",#x,x);
//#define debug(x) cout << #x << ": " << x << endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=700+7;
const int mod =1e9+7;
ll dp[maxn][maxn][3][3];
int a[maxn];
stack<int>sta;
char s[maxn];

void dfs(int i,int j) {
    if(i>=j) return ;
//    printf("i=%d j=%d
",i,j);
    if (i + 1 == j) {
        dp[i][j][0][1] = dp[i][j][0][2] = 1;
        dp[i][j][1][0] = dp[i][j][2][0] = 1;
    }
    else if (a[i] == j) {
        dfs(i + 1, j - 1);
        for (int x = 0; x <= 3; x++) {
            for (int y = 0; y < 3; y++) {
                if (x != 1) {
                    dp[i][j][1][0] += dp[i+1][j-1][x][y];
                    dp[i][j][1][0] %= mod;
                }
                if (x != 2) {
                    dp[i][j][2][0] += dp[i+1][j-1][x][y];
                    dp[i][j][2][0] %= mod;
                }
                if (y != 1) {
                    dp[i][j][0][1] += dp[i+1][j-1][x][y];
                    dp[i][j][0][1] %= mod;
                }
                if (y != 2) {
                    dp[i][j][0][2] += dp[i+1][j-1][x][y];
                    dp[i][j][0][2] %= mod;
                }
            }
        }
    } else {
        int p = a[i];
        dfs(i,p),dfs(p+1,j);
        for (int x = 0; x < 3; x++) {
            for (int y = 0; y < 3; y++) {
                for (int k = 0; k < 3; k++) {
                    for (int t = 0; t < 3; t++) {
                        if (k == t && t != 0) continue;
                        dp[i][j][x][y] += dp[i][p][x][k] * dp[p + 1][j][t][y]%mod;
                        dp[i][j][x][y]%=mod;
//                        printf("dp[%d][%d][%d][%d]=%lld k=%d t=%d p=%d
",i,j,x,y,dp[i][j][x][y],k,t,p);
                    }
                }
            }
        }
    }
//    ll ans=0;
//    for (int x = 0; x <= 3; x++) {
//        for (int y = 0; y < 3; y++) {
//            ans=(ans+dp[i][j][x][y])%mod;
//        }
//    }
//    printf("i=%d j=%d ans=%lld
",i,j,ans);
}

int main(){
    scanf("%s",s+1);
    int n = strlen(s+1);
    for(int i=1;i<=n;i++){
        if(s[i]=='(') sta.push(i);
        else {
            int u = sta.top();sta.pop();
            a[u]=i,a[i]=u;
        }
    }
    dfs(1,n);
    ll ans=0;
    for (int x = 0; x <= 3; x++) {
        for (int y = 0; y < 3; y++) {
            ans=(ans+dp[1][n][x][y])%mod;
        }
    }
    printf("%lld
",ans);
    return 0;
}