中石油网页设计与网站建设,什么语言做网站快,代理登陆网站,软件开发专业属于哪个专业大类题干#xff1a;
小w很生气
小w有一个长为n的括号序列 愤怒小w想把这个括号序列分为两个括号序列 小w想让分为的这两个括号序列同时合法 小w想知道一共有多少种划分方案
(划分的意思是划分为两个子序列)
注意两个序列是 A,B 和 两个序列是B,A 算两种方案,也就是同一位置位…题干
小w很生气
小w有一个长为n的括号序列 愤怒小w想把这个括号序列分为两个括号序列 小w想让分为的这两个括号序列同时合法 小w想知道一共有多少种划分方案
(划分的意思是划分为两个子序列)
注意两个序列是 A,B 和 两个序列是B,A 算两种方案,也就是同一位置位于不同划分为方案不同
输入描述:
第一行一正整数n
第二行,一串长为n的括号序列
输出描述:
一个正整数
表示对方案数对2333取mod后的方案数
示例1
输入
复制
4
(())
输出
复制
6
示例2
输入
复制
8
()()()()
输出
复制
16
备注:
n ≤ 10000
解题报告
就是求括号匹配个数。dp[i][j]表示长度为i的表达式左括号比右括号多j个的情况数。那么ansdp[len][0]。注意第二层循环要遍历到sum[i]不能直接跑到10000这样也就意味着比如可以从非法的dp[i][500]加上500个从而更新到了f[j][0]
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#includecctype
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX 2e5 5;
char s[MAX];
int dp[10005][10005];//dp[i][j]代表前i个序列中左括号比有括号多j个 的方案数。
const int mod 2333;
int sum[10009];
int main() {int n;cinn;scanf(%s,s1);int len strlen(s1);dp[0][0]1;for(int j 1; jn; j) {if(s[j]()sum[j]sum[j-1]1;else sum[j]sum[j-1]-1;}for(int i 1; ilen; i) {for(int j 0; jsum[i]; j) {//不选dp[i][j] dp[i-1][j];//选if(s[i] ( j0) dp[i][j] dp[i-1][j-1];if(s[i] )) dp[i][j] dp[i-1][j1];dp[i][j]%mod;}}printf(%d\n,dp[len][0]);return 0 ;
}
滚动数组优化
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#includecctype
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX 2e5 5;
char s[MAX];
int dp[2][10005];//dp[i][j]代表前i个序列中左括号比有括号多j个 的方案数。
int qq[100000000];
const int mod 2333;
int sum[10009];
int main() {int n;cinn;scanf(%s,s1);int len strlen(s1);dp[0][0]1;for(int j 1; jn; j) {if(s[j]()sum[j]sum[j-1]1;else sum[j]sum[j-1]-1;}int flag 0;for(int i 1; ilen; i) {flag ^ 1;for(int j 0; jsum[i]; j) {//不选dp[flag][j] dp[flag^1][j];//选if(s[i] ( j0) dp[flag][j] dp[flag^1][j-1];if(s[i] )) dp[flag][j] dp[flag^1][j1];dp[flag][j]%mod;}memset(dp[flag^1],0,sizeof dp[flag^1]);}printf(%d\n,dp[flag][0]);return 0 ;
}
注意别忘每次循环完了之后都memset一下
