CF149D

BerlandsFD · 2024-01-25 10:41:40 · 个人记录

题目链接：CF149D

思路

用递归一层一层地枚举括号。对于每个括号，合法方案数等于它内部的第一个括号的合法方案数乘上内部其他括号的合法方案数。

用四维 dp_{i,j,a,b} 表示区间 i 到 j 中首位为 a 颜色末位为 b 颜色的方案数。

Code

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int mod = 1e9 + 7;
string s;
ll dp[710][710][5][5], len;

ll dp_dfs(int l, int r, int a, int b)
{
    if (dp[l][r][a][b]) return dp[l][r][a][b];
    if (l >= r) // 搜完了
    {
        if (a == 0 || b == 0 || a != b) return 1; //颜色不同
        else return 0; //颜色相同
    }
//记录第一个括号的位置
    int tmp = 0, pos = 0;
    for (int i = l; i <= r; i++)
    {
        if (s[i] == '(') tmp++;
        else tmp--;
        if (tmp == 0)
        {
            pos = i;
            break;
        }
    }
    ll ans = 0;
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            if (!((i == 0 && j != 0) || (i != 0 && j == 0))) continue; // 两个括号颜色不能相同
            if (!((a == 0 && i == 0) || a != i)) continue; // 相连的两个括号颜色不能相同
            ans = (ans + (dp_dfs(l + 1, pos - 1, i, j) % mod * dp_dfs(pos + 1, r, j, b) % mod) % mod) % mod;
        }
    }
    return dp[l][r][a][b] = ans;
}

int main()
{
    cin >> s;
    len = s.size();
    cout << dp_dfs(0, len - 1, 0, 0) << endl;
    return 0;
}