当前位置：首页 > news >正文

CodeForces149D dfs实现区间dp

news 来源：原创 2024/5/19 21:51:17

http://codeforces.com/problemset/problem/149/D

题意给一个合法的括号串，然后问这串括号有多少种涂色方案，当然啦！涂色是有限制的。

　　1,每个括号只有三种选择：涂红色，涂蓝色，不涂色。

　　2,每对括号有且仅有其中一个被涂色。

　　3,相邻的括号不能涂相同的颜色，但是相邻的括号可以同时不涂色。

当dp的状态转移方程实现比较复杂的时候的时候，我们不需要非要写出他的状态转移方程，而是通过dfs的方式实现状态的转移。

这句话在之前写的状压dp三进制解法中出现过 https://www.cnblogs.com/Hugh-Locke/p/9499717.html

想了很久的dp递推式，发现是区间dp的时候依然觉得不能像寻常区间dp一样两端的去扩展，在这种时候可以考虑用dfs去实现

任何括号字符串都可以分为两类 ((((())))) 这样的和 ()()()()()这样的，第一种我们考虑两边层层推入，搜索dfs(l + 1,r - 1)之后去递推。

第二种我们考虑分而治之，分为两边互为独立的括号区间然后合并，比如分为()和()()()()合并的方式是两边相乘。

dp边界,也就是当我们最终把两类简化到不能再简化的时候，都会变成()

区间dp+dfs，又有点像记忆化搜索的方式实现即可。

#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++)  
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))  
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Scl(x) scanf("%lld",&x);  
#define Pri(x) printf("%d\n", x)
#define Prl(x) printf("%lld\n",x);  
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long  
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second 
typedef vector<int> VI;
const double eps = 1e-9;
const int maxn = 710;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7; 
int N,M,tmp,K,len; 
char str[maxn];
int link[maxn];
int Stack[maxn];
LL dp[maxn][maxn][3][3];
void find(){
    int cnt = 0;
    For(i,1,len){
        if(str[i] == '('){
            Stack[++cnt] = i;
        }else{
            link[i] = Stack[cnt];
            link[Stack[cnt--]] = i;
        }
    }
}
void dfs(int l,int r){
    if(l == r - 1){
        dp[l][r][1][0] = 1;
        dp[l][r][0][1] = 1;
        dp[l][r][2][0] = 1;
        dp[l][r][0][2] = 1;
        return;
    }
    if(link[l] == r){
        dfs(l + 1,r - 1);
        For(i,0,2){
            For(j,0,2){
                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;
                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;
            }
        }
    }else{
        int m = link[l];
        dfs(l,m); dfs(m + 1,r);
        For(i,0,2){
            For(j,0,2){
                For(x,0,2){
                    For(y,0,2){
                        if(j && (j == x)) continue;
                        dp[l][r][i][y] = (dp[l][r][i][y] + dp[l][m][i][j] * dp[m + 1][r][x][y]) % mod;
                    }
                }
            }
        }
    }
}
int main()
{
    scanf("%s",str + 1);
    len = strlen(str + 1);
    find();
    dfs(1,len);
    LL sum = 0;
    For(i,0,2){
        For(j,0,2){
            sum += dp[1][len][i][j]; sum %= mod;
        }
    }
    Prl(sum);
    #ifdef VSCode
    system("pause");
    #endif
    return 0;
}