题解：P10161 [DTCPC 2024] 小方的疑惑 10

· · 题解

好题，我不会，竟然是背包思想的 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;
}

:::