题目链接：点击打开链接
题意：给出一个括号序列，该序列保证是合法的，即每个括号都能找到唯一的一个匹配括号。给出下列三个染色规则，问有多少种染色情况？
1.每个括号要么不涂色，要么涂红色或者蓝色。
2.每一对匹配括号，必须有一个且仅有一个被涂色。
3.两个相邻的括号不能有相同的颜色。（若两者均未涂色也可以）
思路：之前做过最大匹配括号数目的题目，是区间DP问题，此题也可以采用区间DP来做，因为对于每个括号与之匹配的括号是唯一的，所以要事先找到每个括号的匹配括号再进行DP。dp数组开到四维，dp[le][rig][i][j]表示re到rig这个区间的括号，当le、rig位置的括号分别为i、j颜色时的染色种类数。颜色用0、1、2表示不涂色、涂红色、涂蓝色。dp过程，当re和rig直接匹配，直接去递归处理（re + 1，rig - 1）区间，利用（re + 1，rig - 1）区间的相关信息更新dp[re][rig][...][...]；否则，则递归处理（le，m[le]）、（m[le] + 1，rig）区间，再去更新dp[re][rig][...][...]。具体的思路代码可见。
// CodeForces 149D Coloring Brackets.cpp 运行/限制：62ms/2000ms #include <cstdio> #include <cstring> #include <iostream> #include <stack> using namespace std; #define MOD 1000000007 char s[800]; int len,m[800];//m存储匹配结果 stack<int> st;//用于匹配算法 long long dp[800][800][3][3];//le rig color_at_le color_at_rig void match() {//利用栈进行括号匹配算法 for (int i = 0; i < len; i++) { if (s[i] == '(') { st.push(i); } else { int t = st.top(); st.pop(); m[t] = i; m[i] = t; } } } void DP(int le, int rig) { if (le + 1 == rig) {//一对匹配括号染色只有四种情况（0，1），（1，0），（0，2），（2，0） dp[le][rig][0][1] = dp[le][rig][1][0] = 1; dp[le][rig][0][2] = dp[le][rig][2][0] = 1; return; } if (m[le] == rig) {//左右边界括号匹配 DP(le + 1, rig - 1); for (int i = 0; i < 3; i++) {//枚举le + 1位置处的颜色 for (int j = 0; j < 3; j++) {//枚举rig - 1处的颜色 //更新le,rig的（0，1）情况 if(j != 1) dp[le][rig][0][1] = (dp[le][rig][0][1] + dp[le + 1][rig - 1][i][j]) % MOD; //更新le,rig的（1，0）情况 if(i != 1) dp[le][rig][1][0] = (dp[le][rig][1][0] + dp[le + 1][rig - 1][i][j]) % MOD; //更新le,rig的（0，2）情况 if(j != 2) dp[le][rig][0][2] = (dp[le][rig][0][2] + dp[le + 1][rig - 1][i][j]) % MOD; //更新le,rig的（2，0）情况 if(i != 2) dp[le][rig][2][0] = (dp[le][rig][2][0] + dp[le + 1][rig - 1][i][j]) % MOD; } } } else {//左右边界括号不匹配 DP(le, m[le]); DP(m[le] + 1, rig); for (int i = 0; i < 3; i++) {//枚举le位置处颜色 for (int j = 0; j < 3; j++) {//枚举m[le]位置处颜色 for (int t = 0; t < 3; t++) {//枚举m[le] + 1位置处颜色 for (int w = 0; w < 3; w++) {//枚举rig位置处的颜色 if (j == 1 && t == 1 || j == 2 && t == 2) continue; dp[le][rig][i][w] = (dp[le][rig][i][w] + dp[le][m[le]][i][j] * dp[m[le] + 1][rig][t][w]) % MOD; } } } } } } int main(){ while (scanf("%s", s) != EOF) { len = strlen(s); match(); memset(dp, 0, sizeof(dp)); DP(0,len - 1); long long re = 0; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { re = (re + dp[0][len - 1][i][j]) % MOD; } } printf("%I64d\n", re); } return 0; }
