您的位置: 首页  >  IT文章  >  牛牛数括号（DP）

牛牛数括号（DP）

分类: IT文章 • 2022-03-04 23:07:39

牛牛数括号（DP）

链接：https://ac.nowcoder.com/acm/problem/21652

来源：牛客网

题目描述

牛牛最近开始学括号匹配口拉
给你两个括号序列，不保证合法，求有多少种不同的方法可以将两个括号序列合并成一个合法的括号序列
合并的时候不能改变各自序列原先的顺序

输入描述:

输入两行包含两个字符串s1,s2

1 ≤  |s1|,|s2| ≤ 2500

输出描述:

输出一个整数，mod 1e9+7

具体思路：

dp[i][j]表示第一个字符串前i个和第二个字符前j个在'('比')'多的前提下的方案数；这个过程中需要另外开一个数组用来记录这个过程。

然后就爆内存了；打一个滚动数组就好了。

MLE代码：

 1 #pragma comment(linker, "/STACK:102400000,102400000")
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 # define ll long long
 5 # define inf 0x3f3f3f3f
 6 # define ll_inf (1ll<<60)
 7 # define lson l,mid,rt<<1
 8 # define rson mid+1,r,rt<<1|1
 9 const int maxn = 2500+10;
10 const int  N = 15;
11 const int mod = 1e9+7;
12 ll dp[maxn][maxn];
13 int pre[maxn][maxn];
14 char str1[maxn],str2[maxn];
15 int main()
16 {
17     scanf("%s",str1+1);
18     scanf("%s",str2+1);
19     int len1=strlen(str1+1);
20     int len2=strlen(str2+1);
21     dp[0][0]=1;
22     for(int i=0; i<=len1; i++)
23     {
24         for(int j=0; j<=len2; j++)
25         {
26             if(!i&&!j)continue;
27             if(!j)pre[i][j]=pre[i-1][j]+(str1[i]=='('?1:-1);
28             else pre[i][j]=pre[i][j-1]+(str2[j]=='('?1:-1);
29             if(pre[i][j]<0)// 如果第一个字符串前i个 和第二个字符串前j个凑出来的小于0，非法
30                 continue;
31             if(i)
32                 dp[i][j]+=dp[i-1][j];
33             if(j)
34                 dp[i][j]+=dp[i][j-1];
35                 dp[i][j]%=mod;
36         }
37     }
38     printf("%lld
",pre[len1][len2]==0?dp[len1][len2]:0);
39     return 0;
40 }

AC代码：

 1 #pragma comment(linker, "/STACK:102400000,102400000")
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 # define ll long long
 5 # define inf 0x3f3f3f3f
 6 # define ll_inf (1ll<<60)
 7 # define lson l,mid,rt<<1
 8 # define rson mid+1,r,rt<<1|1
 9 const int maxn = 2500+10;
10 const int  N = 15;
11 const int mod = 1e9+7;
12 int dp[3][maxn];
13 int pre[3][maxn];
14 char str1[maxn],str2[maxn];
15 int main()
16 {
17     scanf("%s",str1+1);
18     scanf("%s",str2+1);
19     int len1=strlen(str1+1);
20     int len2=strlen(str2+1);
21     int cur=0;
22     dp[cur][0]=1;
23     for(int i=0; i<=len1; i++)
24     {
25         if(i)
26         {
27             cur^=1;
28             memset(dp[cur],0,sizeof(dp[cur]));
29         }
30         // pre[i][0]=
31         for(int j=0; j<=len2; j++)
32         {
33             if(!i&&!j)
34                 continue;
35             if(!j)
36                 pre[cur][j]=pre[cur^1][j]+(str1[i]=='('?1:-1);
37             else
38                 pre[cur][j]=pre[cur][j-1]+(str2[j]=='('?1:-1);
39             if(pre[cur][j]<0)
40                 continue;
41             if(i)
42                 dp[cur][j]+=dp[cur^1][j];
43             if(j)
44                 dp[cur][j]+=dp[cur][j-1];
45             dp[cur][j]%=mod;
46         }
47     }
48     printf("%d
",pre[cur][len2]==0?dp[cur][len2]:0);
49     return 0;
50 }

学习网址：https://blog.csdn.net/j2_o2/article/details/87971817#commentBox

相关推荐