区间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); }