Codeforces 149 D Coloring Brackets(区间dp,标记状态，dfs)_综合

题目链接：
Codeforces 149 D Coloring Brackets
题意：
给一个正确匹配的圆括号字符串，比如: $(), (()),(()())$ ，要对括号进行染色：

对每个括号可以选择不染色，染红色，或者染蓝色
每对匹配的括号必须有且仅有一个染色
相邻染色的括号的颜色不能一样

求最终的所有染色方案数？结果对 $1e9+7$ 取模。
数据范围：字符串长度： $2\leq |s|\leq 700$
分析：
区间dp，可能比较容易想到，但是能想到标记状态和递归求解就比较难(?)了。。。。=_+
利用栈的思想可以获取每个括号的匹配括号的位置。
首先用0，1，2分别表示没被染色、被染成红色和被染成蓝色。
用 $dp[a][b][s][e]$ 表示区间 $[a,b]$ 且 $s[a]$ 状态为 $s$ ， $s[b]$ 状态为 $e$ 的所有方案数。做的时候总想着如何避免相邻颜色不一致和三层循环写 $dp$ 如何枚举 $k$ ，没想到状态标记和递归。

当

s[a]和s[b] $s[a]和s[b]$ 是匹配括号时，只需要枚举

s[a]和s[b] $s[a]和s[b]$ 的所有匹配情况然后递归求解区间

[a+1,b?1] $[a+1,b-1]$ ，但是要保证

s[a+1]和s[a] $s[a+1]和s[a]$ 以及

s[b?1]和s[b] $s[b-1]和s[b]$ 的颜色都不能一样。

当 $s[a]和s[b]$ 不是匹配括号时，需要找到 $s[a]$ 的匹配括号位置 $mid$ ,然后递归处理区间 $[a,mid],[mid +1,b]$ ，两者相乘即可。

时间复杂度： $O(9*n^2)$

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cassert>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;
const int MAX_N = 710;
const ll mod = (ll)(1e9) + 7;int n, top;
char s[MAX_N];
ll dp[MAX_N][MAX_N][3][3];
int good[3][3], bad[3][3], match[MAX_N], sta[MAX_N];ll BiuBiu(int a, int b, int s, int e)
{if (dp[a][b][s][e] != -1) return dp[a][b][s][e];if (a + 1 == b) return dp[a][b][s][e] = (good[s][e] ? 1 : 0);ll res = 0;if (match[a] == b) {if (!good[s][e]) return dp[a][b][s][e] = 0;for (int i = 0; i < 3; ++i) {if (bad[s][i]) continue;for (int j = 0; j < 3; ++j) {if (bad[j][e]) continue;res = (res + BiuBiu(a + 1, b - 1, i, j)) % mod;}}} else {int mid = match[a];for (int i = 0; i < 3; ++i) {for (int j = 0; j < 3; ++j) {if (bad[i][j]) continue;res = (res + BiuBiu(a, mid, s, i) * BiuBiu(mid + 1, b, j, e)) % mod;}}}return dp[a][b][s][e] = res;
}int main()
{good[0][1] = good[1][0] = good[0][2] = good[2][0] = 1;bad[1][1] = bad[2][2] = 1;while (~scanf("%s", s)) {n = strlen(s);top = 0;for (int i = 0; i < n; ++i) {if (s[i] == '(') sta[++top] = i;else {match[sta[top]] = i;match[i] = sta[top];--top;}}memset(dp, -1, sizeof (dp));ll ans = 0;for (int i = 0; i < 3; ++i) {for (int j = 0; j < 3; ++j) {ans = (ans + BiuBiu(0, n - 1, i, j)) % mod;//printf("i = %d j = %d ans = %lld\n", i, j, ans);}}printf("%lld\n", ans);}return 0;
}