题目链接
这是一道区间dp的题目……怎么说呢，让我认识到我之前对区间dp的理解太浅显和模式化了，总觉得就是枚举每个区间段就可以了， ==确实是我刷的题还太少。 这道题目也是对于这些颜色该怎么处理无从下手，看完题解才觉得好巧妙。dp[rl[r][prel][prer]，用这个数组来表示每个区间的状态，prel prer即代表这个区间外的紧挨的两个括号的颜色，有三种状态0 1 2，0为不染色，1为红色，2为蓝色。
而对于每一个区间，要怎么划分它的子问题呢，并不是可以看成任意两段的组合，这两段的问题一定是不重叠的，所以，只有与左括号或者右括号的匹配的那个地方才是可以划分的，由于这两种情况下一段一段的分下去最后结果一定是一样的，所以取哪一个都可以。 然后通过枚举括号的颜色，来继续求解问题。 最后的结果即为dp[1][n][0][0]，相当于给外围加了两个没有颜色的括号，并不影响结果。
#include<cstdio> #include<cstdlib> #include<cstring> #include <cmath> #include<iostream> #include<algorithm> #include <vector> #include <bitset> #include <stack> #define maxn 710 #define ll long long #define MEM(x,num) memset(x,num,sizeof(x)) #define inf 0x3f3f3f3f #define mod 1000000007 using namespace std; char s[maxn]; ll dp[maxn][maxn][3][3]; //0不染色 1红色 2蓝色 int match[maxn]; int n; void init() { stack<int> st; for(int i=1;i<=n;i++) { if(s[i]=='(') st.push(i); else { int a=st.top(); st.pop(); match[a]=i; match[i]=a; } } } ll solve(int l,int r,int prel,int prer) //prel prer分别代表l r之前的那个区间的颜色 { ll & ans=dp[l][r][prel][prer]; if(ans!=-1) return ans; if(l>=r) return ans=1; ans=0; int x=match[r]; for(int le=0;le<3;le++) //枚举x的颜色 for(int ri=0;ri<3;ri++) if(ri&&!le||le&&!ri) { if(ri&&ri==prer) continue; if(x==l&&le&&le==prel) continue; ans=(ans+solve(l,x-1,prel,le)*solve(x+1,r-1,le,ri))%mod; } return ans; } int main() { scanf("%s",s+1); memset(dp,-1,sizeof(dp)); n=strlen(s+1); init(); cout<<solve(1,n,0,0)<<endl; return 0; }