区间dp

我想起了雨神说的一句话，dp问题没有什么难的，只要你能把他们之间的关系理清楚就好了

同样这一题算是超级麻烦了
因为不可以两个括号染上相同的颜色这一个特殊条件，我们在进行区间dp的过程中，必须也同时记录两端的颜***r>把所需求解的信息都记录下来。

#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
ll dp[710][710][3][3];
int pre[710];
char s[710];
int n;

int main(){
    scanf("%s",s+1);
    n = strlen(s+1);
    for (int i=1;i<=n;++i){
        pre[i]=pre[i-1];
        if (s[i]=='(')++pre[i];
        else --pre[i];
    }
    for (int i=1;i<n;++i)
        if (s[i]=='('&&s[i+1]==')')
            dp[i][i+1][0][1]=dp[i][i+1][0][2]=dp[i][i+1][1][0]=dp[i][i+1][2][0]=1;

    vector<int> v;
    for (int p=4;p<=n;++p){
        for (int i=1,j=i+p-1;j<=n;++i,++j){
            if(pre[j]-pre[i-1]!=0)continue;
            int judge = 0;v.clear();
            for (int k=i;k<=j;++k){
                judge=min(judge,pre[k]-pre[i-1]);
                if (pre[k]-pre[i-1]==0)v.push_back(k);
            }
            if (judge<0)continue;
            if (v.size()==1){
                for (int k=0;k<3;++k){
                    dp[i][j][1][0]=(dp[i][j][1][0]+dp[i+1][j-1][0][k]+dp[i+1][j-1][2][k])%mod;
                    dp[i][j][2][0]=(dp[i][j][2][0]+dp[i+1][j-1][0][k]+dp[i+1][j-1][1][k])%mod;
                    dp[i][j][0][1]=(dp[i][j][0][1]+dp[i+1][j-1][k][0]+dp[i+1][j-1][k][2])%mod;
                    dp[i][j][0][2]=(dp[i][j][0][2]+dp[i+1][j-1][k][0]+dp[i+1][j-1][k][1])%mod;
                }
            }
            else{
                v.pop_back();
                int k = v.back();
                for (int t=0;t<3;++t){
                    for (int o=0;o<3;++o){
                        if (t!=o||t+o==0){
                        dp[i][j][0][0]=(dp[i][j][0][0]+dp[i][k][0][t]*dp[k+1][j][o][0]%mod)%mod;
                        dp[i][j][1][1]=(dp[i][j][1][1]+dp[i][k][1][t]*dp[k+1][j][o][1]%mod)%mod;
                        dp[i][j][2][2]=(dp[i][j][2][2]+dp[i][k][2][t]*dp[k+1][j][o][2]%mod)%mod;
                        dp[i][j][0][1]=(dp[i][j][0][1]+dp[i][k][0][t]*dp[k+1][j][o][1]%mod)%mod;
                        dp[i][j][0][2]=(dp[i][j][0][2]+dp[i][k][0][t]*dp[k+1][j][o][2]%mod)%mod;
                        dp[i][j][1][0]=(dp[i][j][1][0]+dp[i][k][1][t]*dp[k+1][j][o][0]%mod)%mod;
                        dp[i][j][2][0]=(dp[i][j][2][0]+dp[i][k][2][t]*dp[k+1][j][o][0]%mod)%mod;
                        dp[i][j][1][2]=(dp[i][j][1][2]+dp[i][k][1][t]*dp[k+1][j][o][2]%mod)%mod;
                        dp[i][j][2][1]=(dp[i][j][2][1]+dp[i][k][2][t]*dp[k+1][j][o][1]%mod)%mod;
                        }
                    }
                }
            }
        }
    }
    ll ans = 0;
    for (int i=0;i<3;++i){
        for (int j=0;j<3;++j){
            ans = (ans+dp[1][n][i][j])%mod;
        }
    }printf("%lld\n",ans);
}