链接：https://www.nowcoder.com/acm/contest/188/D
来源：牛客网
第一行一正整数n
第二行,一串长为n的括号序列
一个正整数
表示对方案数对2333取mod后的方案数
n ≤ 10000
想法:
1 把‘(‘看作是1,‘)‘看作是-1;
2 维护A序列的前缀和 dp[i][k] : 对于在前i个字符中取子序列作为A,其和为k的方法有多少种
??: k只可以为正,想一想为负的话就会为非法序列
还有假设前i个元素 有k1个‘(‘,和k2个‘)‘; 那么k的取值范围为(0~k1-k2),若‘(‘>k1-k2,就会非法
3对于每一个元素我们有两种选择取或不取
dp[i][k]=dp[i-1][k]+dp[i-1][k-1] str[i]=‘(‘;
dp[i][k]=dp[i-1][k]+dp[i-1][k+1] str[i]=‘)‘;
#include <bits/stdc++.h> using namespace std; const int N=1e4+7; const int mod=2333; int dp[2][N]; char str[N]; int n; int main () { scanf ("%d %s",&n,str); int k=0,top=0; dp[0][0]=1; for (int i=0;i<n;i++) { if (str[i]==‘(‘) { top++; dp[k^1][0]=dp[k][0]; for (int j=1;j<=top;j++) dp[k^1][j]=(dp[k][j]+dp[k][j-1])%mod; } else { top--; for (int j=0;j<=top;j++) dp[k^1][j]=(dp[k][j]+dp[k][j+1])%mod; } memset (dp[k],0,sizeof(dp[k])); k=(k^1); } printf("%d\n", dp[k][0]); return 0; }
2018牛客27---D---愤怒: (有关子序列的dp问题)
原文：https://www.cnblogs.com/xidian-mao/p/9784110.html