写在最前：推一下蒟蒻 $\color{limegreen}{blog}$

原题链接~

首先，膜拜搬题人 $\color{black}\texttt{s}\color{red}\texttt{henmadongdong}$ ，他是我们的红太阳！

其次，强烈谴责出题人自己卡常的恶劣行径。

本文阐（fan）述（yi）官方 std 做法，你会发现它的复杂度是假的，具体一会再说。

题意不用表述了，很清楚。

以下论述中，我们把不合法括号串归为一类，即 左括号数目多于右括号 的括号串。

（若在某一时刻，右括号多于左括号，那么之后无论怎么加括号，这整个串都 救不回来 了，没有统计意义）

接下来，我们需要证明一个氡西：

『所有 夹杂着方括号（至少有一对）的合法括号串与 纯圆括号 的合法括号串一一对应』

尝试胡乱证明：

  • 对于一个 夹杂着方括号 的合法括号串 $s$ ，我们将里面所有左方括号换成左圆括号，所有右方括号换成右圆括号，最终的结果一定是一个 纯圆括号 的合法括号串。我们设这个新串为 $t$ 。目前只是单向的对应，我们需要建立 双向 。
  • 对于这个 纯圆括号 的合法括号串 $t$ 。 我们将 $s$ 里，所有匹配上的 圆括号 ，在 $t$ 中相应位置标记出来。
  • 在 $t$ 的其它部分中，所有左圆括号换成左方括号，所有右圆括号换成右方括号。最终我们又得到了一个 夹杂着方括号 的合法括号串，显然这个新串就是 $s$ 。

$Q.E.D.$ （这个证明看上去稀奇古怪的）

题目要求我们求 夹杂着方括号 的合法括号串，我们欣欣然把它转化成了 纯圆括号 的合法括号串计数。

之后就是普及- $dp$ 了，根据括号串dp的基本套路（基本法），我们设 $dp _ {i,j}$ 表示：决策到第 $i$ 个位置，当前左括号比右括号 多 $j$ 个的 括号串数目 。（为什么只考虑 $j$ 为正数在文章开头有说）

那么我们就有简单转移柿子（设给定串为 $s$ ）：

结合状态定义很好理解（或许？）。

初始化是 $dp _ {0,0}=0$ （显然） 。

但是我们意识到这样空间开不下，所以可以 滚一滚 。

这样我们就获得了 $\mathcal{O}(n^2)$ 时间复杂度的优秀做法。按理说应该是过不了题的，而要优化起码得从 状态定义 上开刀。

写到这里我横竖想不到更好方法，在极度愤怒的情况下去看了官方题解，结果：

The correct solution is still O(N^2), but we should speed it up by some constant factor.

你在教我做事？

于是打了个 $n$ 方，果然过了，需要手动卡常，不需要吸氧。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;
const int MAX = 3e5 + 7;
const int MOD = 1e9 + 9;
#define lst (i + 1) & 1//用以滚动数组
int dp[2][MAX], N, p;
int main()
{
	ios::sync _ with _ stdio(0);
	cin >> N;
	dp[0][0] = 1;
	for (register int i = 1; i <= N; i++)
	{
		char c;
		cin >> c;
		int M = min(i, N - i);
		//上界，对答案有贡献的 j 需要小于 N-i ，而考虑合理性，j 还需要小于 i 
		for (register int j = 0; j <= M; j++)
		{
			//转移
			if (!j || c == ')')
			{
				dp[i & 1][j] = dp[lst][j + 1];
			}
			else
			{
				dp[i & 1][j] = (dp[lst][j + 1] + dp[lst][j - 1]) % MOD;
			}
		}
	}
	cout << dp[N & 1][0] << '\n';
	return 0;
}

最后更新： 2021年04月19日 11:27

原始链接： https://quest233.github.io/2021/04/17/%E6%B5%85%E8%B0%88%E4%B8%80%E7%B1%BB%E6%9A%B4%E5%8A%9B%E8%BF%87%E9%A2%98%E2%80%94%E2%80%94-BalticOI-2012-Day1-%E6%8B%AC%E5%8F%B7-%E9%A2%98%E8%A7%A3/