NOIP2024集训Day23 DP常见模型3 - 树形

NOIP2024集训Day23 DP常见模型3 - 树形

A. [CSP-S 2021] 括号序列

区间 dp，令 \(f_{l, r}\) 表示从位置 \(l\) 到位置 \(r\) 一共的合法序列总情况数量。

一共有六种不同的转移情况，所以将 \(f_{l, r}\) 扩充到三维。

1. 全是 *
2. (...)
3. (...)**(...)***，左边以括号序列开头，右边以 * 结尾
4. (...)**(...)**(...)，均以括号序列开头和结尾（包含形态二）
5. ***(...)***(...)，左边以 * 开头，右边以括号序列结尾
6. ***(...)**(...)***，左右均以 * 结尾（包含形态一）

转移（序号对应上边的形态）：

1. 直接特判（暴力判断两端的距离是否 \(\le k\)，是的再转移）

2. \(f_{l, r, 1} = (f_{l +1, r - 1, 0} + f_{l + 1, r - 1, 2} + f_{l + 1, r - 1, 3} + f_{l + 1, r - 1, 4}) \times \operatorname{check}(l, r)\)，其中 \(\operatorname{check}(l, r)\) 表示判断 \(l\) 和 \(r\) 是否能匹配括号

3. \(f_{l, r, 2} = \sum\limits_{i = l}^{r -1} f_{l, i, 3} \times f_{i + 1, r, 0}\)

   均以括号序列开头和结尾是 3，右边接一串 *，是 0。

4. \(f_{l, r, 3} = \sum\limits_{i = l}^{r - 1}(f_{l, i, 2} + f_{l, i, 3}) \times f_{i + 1, r, 1} + f_{l, r, 1}\)

   左边以括号序列开头，结尾随便，符合的有 2 和 3，右边界一个括号序列，是 1，还要加上直接一个括号序列的。

5. \(f_{l, r, 4} = \sum\limits_{i = l}^{r - 1}(f_{l, i, 4} + f_{l, i, 5})\times f_{i + 1, r, 1}\)

   左边以 * 开头，结尾随便，符合的有 4 和 5，右边借一个括号序列，是 1。

6. \(f_{l, r, 5} = \sum\limits_{i = l}^{r - 1} f_{l, i, 4} \times f_{i + 1, r, 0} + f_{l, r, 0}\)

   左边以 * 开头，以括号序列结尾，符合的是 4，右边接一串 *，是 0，还要加上全是 * 的。

答案必须是以括号序列开头，括号序列结尾，于是为 \(f_{1, n, 3}\)。

初始化：对于所有的 \(1\le i\le n\)，有 \(f_{i, i - 1, 0} = 1\)。

时间复杂度 \(\Theta(6\times n^3)\) 不到。