CF149D Coloring Brackets

• 2020 年 10 月 31 日
• 筆記
• DP

題目

洛谷
CF

題解

考慮DP

先由範圍盲猜一波 分析複雜度可得: \(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種不同的轉移:

1.l+1=r: 返回x,y是否合法

2.r和l是一對匹配的括弧: (枚舉l+1,r-1的顏色i,j轉移) dp[l][r][x][y]+=dp[l+1][r-1][i][j]

3.沒有關係: (與r匹配的左括弧left[r]一定會出現在l~r之間)

枚舉left[r]的顏色j和left[r]-1的顏色i,然後把兩塊區間的答案乘起來

即:dp[l][r][x][y]+=dp[l][left[r]-1][x][i]*dp[left[r]][r][j][y]

然後就是一堆判顏色合法的細節

程式碼

#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;
}