自动搬运

查看原文

来自洛谷，原作者为

	lcfollower 不 AK Div.2 & 3 不改签 | AT 不上蓝不改签（目前只有绿）。 | 不拿蓝钩不改签。 | 大号在 N 个月前已清关，误清的用这个号回关

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

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

以下是正文

---

好题，我不会，竟然是背包思想的 DP。

:::info[一个括号序列里的合法括号序列个数怎么算？]{open}

如果有 $x$ 对括号并列，比如 $\texttt{()()()()}$ 时 $x = 4$，那么有多少个合法的括号序列？

容易发现答案为 $4 + 3 + 2 + 1 = 10$，推广到 $x\in \mathbb{N^*}$，合法的括号序列个数即为 $\frac{x(x+1)}{2}$。

再考虑如果有括号嵌套，先来一种简单的：$\texttt{(()()()())}$，此时里面有 $x = 4$ 个括号并列，外层有 $1$ 个括号包裹，容易发现答案数量为 $10 + 1 = 11$，这个 $1$ 是整个括号序列，稍微手玩一下就会发现不存在任何前缀或者后缀（除了整个括号序列）使得组成的括号序列合法（左括号与右括号个数不等），这些真前缀和真后缀都是比 $\texttt{()()()()}$ 多出来的括号序列，所以可以直接证明。容易推广合法括号序列个数为 $\frac{x(x+1)}{2} + 1$，其中 $1$ 也可以写作 $\frac{1\times 2}{2}$。

然后还有 $\texttt{(()()()())()()()}$，容易发现是上面这种情况的推广，但是我们换一种角度，这是由 $x = 4$ 个“大”括号组成，其中一个“大”括号里面有 $y = 4$ 个小括号并列，同样可以计算多出来的合法括号序列个数，还是同上，可以发现总个数为 $20$（具体省略），容易推广个数为 $\frac{x(x+1)}{2} + \frac{y(y+1)}{2}$。

最后我们将上述的情况混合，比如 $\color{red}{(}\color{blue}{()()()()}\color{red}{)(}\color{green}{()()()}\color{red}{)}\color{purple}{()()()}$，可以发现合法的括号序列个数为红、蓝、绿、紫三种颜色的括号并列，它们的答案（就是 $\frac{x(x+1)}{2}$）之和。

:::

这样就很明确了，我们设 $a_i$ 为 $i$ 个括号并列时的合法括号序列个数（即 $\frac{i(i+1)}{2}$）。接着我们设 $f_i$ 为恰好存在 $i$ 个合法的括号序列的最短序列长度，初始化 $f_0 = 0$，$f_i = +\infty$（$1\le i\le 10^5$）。则转移如下：

$$f_i = \min\limits_{a_j\le i} f_{i - a_j} + 2\times j $$

我们发现这是一个背包模型，因此我们可以用背包的转移方式。

设我们需要预处理 $a$ 的长度为 $x$，因为 $\frac{x(x+1)}{2}\le 10^5$（不然肯定没有意义），因此得到 $x$ 的范围为 $2\times \sqrt{10^5}$ 左右，这样转移是 $\mathcal O(V\sqrt{V})$，其中 $V = 10^5$，不会超时。

然后对于询问 $(n ,k)$，如果 $f_k > n$ 则一定无解。

否则考虑怎么输出一个合法的括号序列，我们用 $lst_i$ 表示有 $i$ 个合法的括号序列，最少需要几对并列的括号。

在输出方案数的时候，我们用递归的形式输出，我们可以在第一个括号里面摆上剩下的括号，然后第 $2\sim lst_k$ 个括号里面不加东西，因为答案是和的形式嘛。

最后如果发现有多余长度没有摆上任何括号，剩下的我们直接输出 ( 即可，这样构不成任何合法的括号序列。

分析到这应该明白为啥要最少了，这里留给读者自己思考。

:::info[代码]

inline void print (int k){
    if (!k) return;//没有了就别输出了。
    putchar ('(');//第一个 () 的左括号，要在后面输出一点东西。
    print (k - a[lst[k]]);//剩下的括号递归输出。
    putchar (')');//第一个 () 的右括号，包裹起来。
    up (i ,2 ,lst[k]) putchar ('(') ,putchar (')');//余下的直接输出 ()()()...() 即可。
} inline void solve (){
    n = read () ,k = read ();
    if (f[k] > n) {puts ("-1") ; return ;}//无解。
    print (k);
    up (i ,f[k] + 1 ,n) putchar ('(');//存在剩余括号，全输出 ( 即可。
    puts ("");
} signed main() {
    up (i ,1 ,1e5) {
        if (i * (i + 1) / 2 <= 1e5) a[++ cnt] = i * (i + 1) / 2;//预处理所有可能的长度。
        else break;
    }
    memset (f ,0x3f ,sizeof f);
    f[0] = 0;//初始化。
    up (i ,1 ,cnt)//进行背包模型的转移。
        up (j ,a[i] ,1e5)
            if (f[j] > f[j - a[i]] + 2 * i) {
                f[j] = f[j - a[i]] + 2 * i ,lst[j] = i;//顺便记录 lst。
            }
    int T = read ();
    while (T --) solve ();
    return 0;
}

:::