题干:
小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个的情况数。那么ans=dp[len][0]。注意第二层循环要遍历到sum[i]!!不能直接跑到10000,这样也就意味着,比如可以从非法的dp[i][500],加上500个),从而更新到了f[j][0]?
AC代码:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#include<cctype>
#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;
cin>>n;
scanf("%s",s+1);
int len = strlen(s+1);
dp[0][0]=1;
for(int j = 1; j<=n; j++) {
if(s[j]=='(')sum[j]=sum[j-1]+1;
else sum[j]=sum[j-1]-1;
}
for(int i = 1; i<=len; i++) {
for(int j = 0; j<=sum[i]; j++) {
//不选
dp[i][j] = dp[i-1][j];
//选
if(s[i] == '(' && j>0) dp[i][j] += dp[i-1][j-1];
if(s[i] == ')') dp[i][j] += dp[i-1][j+1];
dp[i][j]%=mod;
}
}
printf("%d\n",dp[len][0]);
return 0 ;
}
滚动数组优化:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#include<cctype>
#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;
cin>>n;
scanf("%s",s+1);
int len = strlen(s+1);
dp[0][0]=1;
for(int j = 1; j<=n; j++) {
if(s[j]=='(')sum[j]=sum[j-1]+1;
else sum[j]=sum[j-1]-1;
}
int flag = 0;
for(int i = 1; i<=len; i++) {
flag ^= 1;
for(int j = 0; j<=sum[i]; j++) {
//不选
dp[flag][j] = dp[flag^1][j];
//选
if(s[i] == '(' && j>0) dp[flag][j] += dp[flag^1][j-1];
if(s[i] == ')') dp[flag][j] += dp[flag^1][j+1];
dp[flag][j]%=mod;
}
memset(dp[flag^1],0,sizeof dp[flag^1]);
}
printf("%d\n",dp[flag][0]);
return 0 ;
}
注意别忘每次循环完了之后都memset一下!