专栏文章

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

cchenwenmo
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minmklug
此快照首次捕获于
2025/12/02 04:52
3 个月前
此快照最后确认于
2025/12/02 04:52
3 个月前
查看原文
若有 mm 个 () 形如这样排列：()()()...。那么合法括号串数是 m(m−1)2\frac{m(m-1)}{2}。
如果把 tt 个 () 形如 ()()()... 放入上述 mm 个 () 的最左边那一个里面，即：(()()()...t)()()...m。则合法括号串数为 m(m−1)2+t(t−1)2\frac{m(m-1)}{2} + \frac{t(t-1)}{2}。
因此我们用背包计算出，凑够 kk 个合法括号串，最短的长度为 ll，然后在末尾补上 n−ln-l 个 ( 即可。
容易用调整法证明，每个合法方案都存在一个这样的等价方案。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...