题解 P7248 【[BalticOI 2012 Day1] 括号】
quest_2
·
·
题解
写在最前：推一下蒟蒻 \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{[]})}
题目要求我们求 **夹杂着方括号** 的合法括号串，我们欣欣然把它转化成了 **纯圆括号** 的合法括号串计数。
之后就是普及- $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$ 方，果然过了，需要手动卡常，不需要吸氧。
代码：
```cpp
#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;
}
```