自动搬运

查看原文

来自洛谷，原作者为

	quest_2 你看你在有些方面那么有天赋，如果将来去打工，真是莫大的遗憾了。

搬运于2025-08-24 22:28:03，当前版本为作者最后更新于2021-01-08 15:12:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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

---

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

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

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

---

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

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

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

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

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

尝试胡乱证明：

• 对于一个 夹杂着方括号 的合法括号串 $s$ ，我们将里面所有左方括号换成左圆括号，所有右方括号换成右圆括号，最终的结果一定是一个 纯圆括号 的合法括号串。我们设这个新串为 $t$ 。目前只是单向的对应，我们需要建立 双向 。

$$\texttt{s:(()\red{[]})}\Rightarrow\texttt{t:(()\red{()})} $$

• 对于这个 纯圆括号 的合法括号串 $t$ 。 我们将 $s$ 里，所有匹配上的 圆括号 ，在 $t$ 中相应位置标记出来。

$$\begin{matrix}\texttt{s:\blue{(()}[]\blue{)}}\\\texttt{t:\blue{(()}()\blue{)}}\end{matrix} $$

• 在 $t$ 的其它部分中，所有左圆括号换成左方括号，所有右圆括号换成右方括号。最终我们又得到了一个 夹杂着方括号 的合法括号串，显然这个新串就是 $s$ 。

$$\texttt{t:(()\red{()})}\Rightarrow\texttt{s:(()\red{[]})} $$

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

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

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

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

$$\begin{cases}dp_{i,j}=dp_{i-1,j+1}\qquad(s[i]=')')\\dp_{i,j}=dp_{i-1,j+1}+dp_{i-1,j-1}\qquad(s[i]='(')\end{cases} $$

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

初始化是 $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$ 方，果然过了，需要手动卡常，不需要吸氧。

代码：

#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;
}