第十二届蓝桥杯省赛c/c++B组-括号序列

Solost

2023 年 03 月 23 日

279 次浏览

1 条评论

1975字数

题目题解

![image.png](https://amarantos.oss-cn-hangzhou.aliyuncs.com/typecho/2023%2F03%2F23%2Fimage.png)

## 题目连接

[题目链接](https://www.acwing.com/problem/content/description/3423/)

## 参考链接

[参考链接](https://blog.csdn.net/weixin_60896526/article/details/125436735?spm=1001.2101.3001.6661.1&utm_medium=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-1-125436735-blog-122726632.235%5Ev27%5Epc_relevant_recovery_v2&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-1-125436735-blog-122726632.235%5Ev27%5Epc_relevant_recovery_v2&utm_relevant_index=1)

[参考链接](https://www.acwing.com/solution/content/75383/)

## 题解

![image(1).png](https://amarantos.oss-cn-hangzhou.aliyuncs.com/typecho/2023%2F03%2F23%2Fimage%281%29.png)

思路应该是计算出要加的左括号数目，然后再镜像字符串计算出需要添加右括号的数目，相乘即可。因为让他变成一个合法的字符串需要左括号的数目大于等于右括号的字符串，我们第一次可以计算出使得右括号一定有的匹配的方法数再乘另一种情况即可。

> `f[i][j]`的状态表示
>
> (1)集合：只考虑前 i 部分，左括号比右括号多 j 个的所有方案的集合(即不同数量的左括号的方案数)
>
> (2)属性：数量
>
> 状态计算：
>
> (1) 若`str[i] == '('`，易推算出转移方程为`f[i][j] = f[i - 1][j - 1]`
>
> (2) 若`str[i] == ')'`，则在只考虑前 i - 1部分时，此时左括号数量最多比右括号多 j + 1个，才可能在第 i 部分通过添加或者不加左括号，达到左括号的数量比右括号多 j 个，故状态转移方程为`f[i][j] = f[i - 1][j + 1] + f[i - 1][j] + ...... + f[i - 1][0]`，通过完全背包的思维优化这一段转移方程，使得该部分总复杂度由 `O(n^3) `降为`O(n^2)`，优化的状态转移方程为`f[i][j] = f[i - 1][j + 1] + f[i][j - 1]` (为了防止越界，`f[i][0]`需要特判)。

```cpp
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>

using namespace std;
#define x first
#define y second
#define endl '\n'
#define IOS
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
typedef long long ll;
typedef pair<int, int> PII;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2e5 + 10;

int f[5010][5010];

int op(string s)
{
    memset(f, 0, sizeof(f));
    f[0][0] = 1;
    int n = s.size();
    s = ' ' + s;
    for (int i = 1; i <= n; i++) {
        if (s[i] == '(') {
            for (int j = 1; j <= n; j++) {
                f[i][j] = f[i - 1][j - 1];
            }
        } else {
            f[i][0] = (f[i - 1][1] + f[i - 1][0]) % mod;
            for (int j = 1; j <= n; j++) {
                f[i][j] = (f[i - 1][j + 1] + f[i][j - 1]) % mod;
            }
        }
    }
    for (int i = 0; i <= n; i++) {
        if (f[n][i])
            return f[n][i];
    }
    return 0;
}

void solve()
{
    string s;
    cin >> s;
    int l = op(s);
    reverse(s.begin(), s.end());
    for (auto& x : s) {
        if (x == ')')
            x = '(';
        else
            x = ')';
    }
    int r = op(s);
    cout << (1ll * l * r) % mod << endl;
}
int main()
{
    // IOS;
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
```

最后修改：2023 年 03 月 24 日