Codeforces 149D. Coloring Brackets

正文索引 [隐藏]

传送门:http://codeforces.com/contest/149/problem/D

题目翻译

一个符合匹配的括号序列,匹配的两个括号只能有一个有颜色(红色或者蓝色),相邻的符号若有颜色颜色不同。求不同的方案数。

题解

区间DP
DP[left][right][lc][rc]表示left~right的区间内左边颜色为lc,右边颜色为rc的方案数。
然后因为有重复,所以我们每次合并左右两个大区间的时候,只选择右边是刚好被一对括号包括的区间。

代码