洛谷
CF
先由范围盲猜一波 分析复杂度可得: \(O(n^2)\)
所以先设 dp[l][r] 表示处理l~r区间的答案
但对于区间l~r的状态而言,显然是不够的,还要再记录l和r的颜色
所以dp[l][r][x][y]表示l颜色为x, r颜色为y (\(0<=x,y<=2\))
具体通过记忆化搜索实现
我们需要在转移的过程中保证l位置始终是"(",r位置")"
对于l,r的不同关系,我们会有3种不同的转移:
然后就是一堆判颜色合法的细节
代码 #include<bits/stdc++.h> using namespace std; #define re register #define in inline #define ll long long #define get getchar() #define right ri #define left le #define int ll const int _=755; const int mod=1e9+7; int st[_]; int n,top,left[_],right[_]; char s[_]; ll dp[_][_][3][3]; in bool check(int l,int r,int x,int y) { if(right[l]!=r) return 1; if(x>0&&y>0) return 0; if(x==0 && y==0) return 0; return 1; } //判断l,r是否合法(若l,r无关系则必定合法) in int dfs(int l,int r,int x,int y) { if(dp[l][r][x][y]) return dp[l][r][x][y]; if(!check(l,r,x,y)) return 0; if(l+1==r){ dp[l][r][x][y]=1; return 1; } for(re int i=0;i<=2;i++) for(re int j=0;j<=2;j++) { if(left[r]==l) { if((j>0 && j==y) || (i>0 && x==i)) continue; dp[l][r][x][y]=(dp[l][r][x][y]+dfs(l+1,r-1,i,j))%mod; } else { if((!check(left[r],r,j,y)) || (!check(l,left[r]-1,x,i))) continue; if(j==i && i>0) continue; dp[l][r][x][y]=(dp[l][r][x][y]+dfs(left[r],r,j,y)*dfs(l,left[r]-1,x,i)%mod)%mod; } } return dp[l][r][x][y]; } signed main() { scanf("%s",s+1); n=strlen(s+1); st[top]=1; for(re int i=2;i<=n;i++) { if(s[i]==')') right[st[top]]=i,left[i]=st[top--]; else st[++top]=i; } //预处理每个括号对应的括号的位置 ll ans=0; for(re int i=0;i<=2;i++) for(re int j=0;j<=2;j++) { ans=(ans+dfs(1,n,i,j))%mod; } cout<<ans<<endl; }