CF149D Coloring Brackets 【动态规划】

区间dp，dp[i][j][l][r] 表示区间i到j里，左端点为l颜色，右端点为r颜色的染色方案数，强制不合法的区间的值为0

转移只会有两种：

当这个的两个端点为配对的连个括号时，直接把区间i+1,j-1的答案拿过来用

当两个端点不配对时，肯定，这段区间肯定是由多个小的区间组成的，但我们并不关心有多少个，只要把大区间从一个合法的位置割开然后计算答案就行了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#define gi get_int()
#define int long long
const int MAXN = 1000, MOD = 1e9 + 7;
int get_int()
{
  int x = 0, y = 1;
  char ch = getchar();
  while (!isdigit(ch) && ch != ‘-‘)
    ch = getchar();
  if (ch == ‘-‘)
    y = -1, ch = getchar();
  while (isdigit(ch))
    x = x * 10 + ch - ‘0‘, ch = getchar();
  return x * y;
}

int dp[MAXN][MAXN][3][3], pos[MAXN];

signed main()
{
  freopen("code.in", "r", stdin);
  freopen("code.out", "w", stdout);

  std::string str;
  std::cin >> str;
  int n = str.size();
  std::stack<int> st;
  for (int i = 0; i < n; i++) {
    if (str[i] == ‘(‘) st.push(i);
    else {
      pos[i] = st.top();
      pos[st.top()] = i;
      st.pop();
    }
  }
  for (int i = 1; i < n; i++)
    if (str[i] == ‘)‘ && str[i - 1] == ‘(‘) {
      dp[i - 1][i][0][2] = dp[i - 1][i][1][2] = dp[i - 1][i][2][0] = dp[i - 1][i][2][1] = 1;
    }
  for (int size = 4; size <= n; size += 2) {
    for (int i = 0; i <= n - size; i++) {
      int j = i + size - 1;
      if (str[i] != ‘(‘ || str[j] != ‘)‘)
        continue;
      if (pos[i] == j) {
        (dp[i][j][0][2] += dp[i + 1][j - 1][1][2] + dp[i + 1][j - 1][2][0] + dp[i + 1][j - 1][2][1] + dp[i + 1][j - 1][1][0] + dp[i + 1][j - 1][2][2] + dp[i + 1][j - 1][1][1]) %= MOD;
        (dp[i][j][1][2] += dp[i + 1][j - 1][0][2] + dp[i + 1][j - 1][2][0] + dp[i + 1][j - 1][2][1] + dp[i + 1][j - 1][0][1] + dp[i + 1][j - 1][2][2] + dp[i + 1][j - 1][0][0]) %= MOD;
        (dp[i][j][2][0] += dp[i + 1][j - 1][2][1] + dp[i + 1][j - 1][0][2] + dp[i + 1][j - 1][1][2] + dp[i + 1][j - 1][0][1] + dp[i + 1][j - 1][2][2] + dp[i + 1][j - 1][1][1]) %= MOD;
        (dp[i][j][2][1] += dp[i + 1][j - 1][2][0] + dp[i + 1][j - 1][0][2] + dp[i + 1][j - 1][1][2] + dp[i + 1][j - 1][1][0] + dp[i + 1][j - 1][2][2] + dp[i + 1][j - 1][0][0]) %= MOD;
      } else {
        int mid = pos[i];
        for (int colorL0 = 0; colorL0 < 3; colorL0++)
          for (int colorR0 = 0; colorR0 < 3; colorR0++)
            for (int colorL1 = 0; colorL1 < 3; colorL1++)
              for (int colorR1 = 0; colorR1 < 3; colorR1++) {
                if (colorR0 == colorL1 && colorR0 != 2) continue;
                (dp[i][j][colorL0][colorR1] += dp[i][mid][colorL0][colorR0] * dp[mid + 1][j][colorL1][colorR1]) %= MOD;
              }
      }
    }
  }
  int ans = 0;
  for (int colorL0 = 0; colorL0 < 3; colorL0++)
    for (int colorR0 = 0; colorR0 < 3; colorR0++) {
      (ans += dp[0][n - 1][colorL0][colorR0]) %= MOD;
    }
  std::cout << ans;
  return 0;
}

CF149D Coloring Brackets 【动态规划】

原文：https://www.cnblogs.com/enisP/p/14817986.html