3420. 括号序列 - AcWing题库
题目描述
题目分析
对于这一我们需要有前缀知识完全背包
完全背包的朴素写法：
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m, v[N], w[N], f[N][N];
int main()
{cin >> n >> m;for(int i = 1; i <= n; i ++)cin >> v[i] >> w[i];for(int i = 1; i <= n; i ++){for(int j = 0; j <= m; j ++){for(int k = 0; k * v[i] <= j; k ++){f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);}}}cout << f[n][m] << '\n';return 0;
}经行优化：
f[i][j] = f[i - 1][j - v[i] * k] + w[i] * k
f[i][j] = max(f[i - 1][j], f[i - 1][j - v] + w, f[i - 1][j - 2v] + 2w, f[i - 1][j - 3v] + 3w, ...)
f[i][j - v] = max( f[i - 1][j - v], f[i - 1][j - 2v] + w, f[i - 1][j - 3v] + 2w, ...)
f[i][j] = max(f[i - 1][j], f[i][j - v] + w)
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m, v[N], w[N], f[N][N];
int main()
{cin >> n >> m;for(int i = 1; i <= n; i ++)cin >> v[i] >> w[i];for(int i = 1; i <= n; i ++){for(int j = 0; j <= m; j ++){for(int k = 0; k * v[i] <= j; k ++){f[i][j] = f[i - 1][j];if(j >= v[i])f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);}}}cout << f[n][m] << '\n';return 0;
}
首先由题意知我们左右括号的数量必须相等，对于任意前缀的左括号的数量必须大于等于有括号的数量（如果小于则此处必定需要添加括号）
我们可以分为两种方案使其独立存在，一种是只添加左括号，一种是只添加右括号，这两种方案各进行一次，将方案数相乘则为总方案数，对于左右进行的操作只需用同一代码即可，我们可以只写对左括号进行操作，对于右括号操作我们只需要将字符串翻转即可实现操作
使用动态规划来记录方案数
f[i][j] ：只考虑前i部分，左括号比右括号多j 个的所有方案的集合（不同数量的左括号的方案数）
1.若s[i] == '(' f[i][j] = f[i - 1][j - 1]（考虑前i - 1部分时，左括号数量比右括号数量多j - 1个，那么第i部分左括号就比右括号多j个）
2.若s[i] == ')' f[i][j] = f[i - 1][j + 1] + f[i - 1][j] + ... + f[i - 1][0]（考虑前i - 1部分左括号数量最多比右括号数量多j + 1个，才能在第i部分通过添加或者不加左括号使左括号的数量比右括号的数量多j个）注：这里类似于完全背包的优化：f[i][j] = f[i - 1][j + 1] + f[i][j - 1]，考虑越界问题，f[i][0]特判(j == 0,j - 1 = -1越界）f[i][0]可以考虑前i - 1部分左括号数和右括号数相等 和 左括号数比右括号数多一个的和
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5010, mod = 1e9 + 7;
char s[N];
int n;
ll f[N][N];
ll work()
{memset(f, 0, sizeof f);f[0][0] = 1;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][0] + f[i - 1][1]) % 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 -1;
}
int main()
{cin >> s + 1;n = strlen(s + 1);ll l = work();reverse(s + 1, s + n + 1);for(int i = 1; i <= n; i ++){if(s[i] == '(')s[i] = ')';else s[i] = '(';}ll r = work();cout << l * r % mod;return 0;
}
