题目描述 小艺酱又得到了一堆括号。 括号是严格匹配的。 现在给括号进行上色。 上色有三个要求: 1、只有三种上色方案,不上色,上红色,上蓝色。 2、每对括号只有一个上色。 3、相邻的两个括号不能上相同的颜色,但是可以都不上色。 问括号上色有多少种方案?答案对1000000007取模。 输入描述: 输入括号序列s。(2<=|s|<=700) 输出描述: 输出方案数。 c++
时间: 2023-02-12 19:59:29 浏览: 96
这道题的解法是使用动态规划。
我们可以用 $dp_{i,j,0/1/2}$ 表示从第 $i$ 个括号到第 $j$ 个括号的子串上色的方案数,其中 0 表示不上色,1 表示上红色,2 表示上蓝色。
对于每个 $dp_{i,j,k}$,我们可以枚举括号的分割点 $p$,然后通过转移方程来计算它的值:
$$dp_{i,j,k}=\sum_{p=i}^{j-1}dp_{i,p,k} \times dp_{p+1,j,k}+\sum_{p=i}^{j-1}\sum_{c=0}^{2}dp_{i,p,k} \times dp_{p+1,j,c}$$
上面的转移方程可以分解成两个部分:
- 左右两侧的括号都不上色(即 $dp_{i,p,k} \times dp_{p+1,j,k}$)
- 左侧括号上色,右侧括号不上色(即 $dp_{i,p,k} \times dp_{p+1,j,c}$,其中 $c$ 是 0 或 1 或 2)
最后,我们要注意在计算答案的时候将所有的 $dp_{i,j,0/1/2}$ 的值加起来,并对1000000007取模。
示例代码如下:
```
const int mod = 1e9 + 7;
int dp[705][705][3];
int main() {
string s;
cin >> s;
int n = s.size();
for (int i = 0; i < n; ++i) {
dp[i][i][0] = 1;
if (s[i] == '(') {
dp[i][i][1] = 1;
} else {
dp[i][i][2] = 1;
}
}
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)