题解：P10161 [DTCPC 2024] 小方的疑惑 10【构造，背包DP】

chenwenmo · 2025-10-12 15:59:41 · 题解

若有 m 个 () 形如这样排列：()()()...。那么合法括号串数是 \frac{m(m-1)}{2}。

如果把 t 个 () 形如 ()()()... 放入上述 m 个 () 的最左边那一个里面，即：(()()()...t)()()...m。则合法括号串数为 \frac{m(m-1)}{2} + \frac{t(t-1)}{2}。

因此我们用背包计算出，凑够 k 个合法括号串，最短的长度为 l，然后在末尾补上 n-l 个 ( 即可。

容易用调整法证明，每个合法方案都存在一个这样的等价方案。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int N = 1e5 + 5, inf = 1e9;

int n, k, w[N], dp[N], pre[N];

void print(int now) {
    if (!now) return;
    int cnt = (dp[now] - dp[pre[now]]) / 2;
    cout << "(";
    print(pre[now]);
    cout << ")";
    for (int i = 1; i < cnt; i++) cout << "()";
}

void Solve() {
    cin >> n >> k;
    if (dp[k] > n) cout << "-1\n";
    else {
        print(k);
        for (int i = 1; i <= n - dp[k]; i++) cout << "(";
        cout << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    for (int i = 1; i <= 1000; i++) w[i] = i * (i + 1) / 2;
    fill(dp + 1, dp + 100000, inf);
    dp[0] = 0;
    for (int i = 1; i <= 1000; i++) {
        for (int j = w[i]; j <= 100000; j++) {
            if (dp[j - w[i]] + i * 2 < dp[j]) {
                dp[j] = dp[j - w[i]] + i * 2;
                pre[j] = j - w[i];
            }
        }
    }

    int T;
    cin >> T;
    while (T--) Solve();
    return 0;
}