网站地图有哪些网址,网站制作客户资料,公司网站建设的作用,网站项目建设管理3420. 括号序列 - AcWing题库
题目描述 题目分析
对于这一我们需要有前缀知识完全背包
完全背包的朴素写法#xff1a;
#includebits/stdc.h
using namespace std;
const int N 1010;
int n, m, v[N], w[N], f[N][N];
int main()
{cin n m;fo…3420. 括号序列 - AcWing题库
题目描述 题目分析
对于这一我们需要有前缀知识完全背包
完全背包的朴素写法
#includebits/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)
#includebits/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部分左括号数和右括号数相等 和 左括号数比右括号数多一个的和
#includebits/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;
}
