Bzoj P2461 [BeiJing2011]符环 题解

每日一题 day65 打卡

因为markdown实在是太麻烦了，所以等开学了再用吧。

Analysis

这道题很有意思，题目有些难懂，主要意思是输入的字符串中第 i 位规定了最后括号序列的第 i 位和第 len+i 位的括号是否相同。

问最后组成了一个合法的括号序列，有多少种情况。

很容易想到的一个做法就是每次枚举是‘（ ’还是‘ ）’。但是因为n最大为50，所以显然是不行的。（复杂度为2^50）

又因为题目只问了情况数没有问具体的情况是什么，所以我们可以考虑用dp数组来表示状态再记忆化搜索，这样时间复杂度就可以保证。

那么现在的问题是，如何在可以接受的空间复杂度内来表示状态？

第一维显然是当前枚举到的字符串的位置。

因为要为了最后能判断是否为合法的括号序列，所以按理来说要再记录四维：1~n左括号未匹配的个数，1~n右括号未匹配的个数，n+1~2n左括号未匹配的个数，n+1~2n右括号未匹配的个数。

这样的话就空间炸了。

那怎么办呢？

我们可以发现，1~n右括号未匹配的个数是没必要记录的，因为如果出现1~n有未匹配的右括号，你无论如何也无法使其最后变为合法。

所以我们可以删掉一维，这样最后的空间复杂度就是50^4，可以接受。

到目前为止，大体思路已经成型了，一些细节我会在代码中为大家讲解。

 1 #include
 2 #include
 3 #include
 4 #include
 5 #define int long long
 6 #define maxn 50+1
 7 #define rep(i,s,e) for(register int i=s;i<=e;++i)
 8 #define dwn(i,s,e) for(register int i=s;i>=e;--i)
 9 using namespace std;
10 inline int read()
11 {
12     int x=0,f=1;
13     char c=getchar();
14     while(c<'0'||c>'9') {if(c=='-') x=-x; c=getchar();}
15     while(c>='0'&&c<='9') {x=x*10+c-'0'; c=getchar();}
16     return f*x;
17 }
18 inline void write(int x)
19 {
20     if(x<0){putchar('-');x=-x;}
21     if(x>9)write(x/10);
22     putchar(x%10+'0');
23 }
24 int t,n,len;
25 char a[maxn];
26 int dp[maxn][maxn][maxn][maxn];
27 int dfs(int now,int x,int y,int z)
28 {
29     if(now==len+1)
30         return z==0&&x==y;//判断是否合法 
31     int &val=dp[now][x][y][z];
32     if(val!=-1) return val;
33     val=0;
34     if(a[now]=='S')
35     {
36         val+=dfs(now+1,x+1,y,z+1);//在1~n和n+1~2n中分别放上一个‘（’ 
37         if(z!=0&&x!=0) val+=dfs(now+1,x-1,y,z-1);//在n+1~2n中有 没有匹配的左括号的情况下，在1~n和n+1~2n中分别放上一个‘）’ 
38         else if(x!=0) val+=dfs(now+1,x-1,y+1,z);//在n+1~2n中没有 没有匹配的左括号的情况下，在1~n和n+1~2n中分别放上一个‘）’
39     }
40     else if(a[now]='D')//与上面同理 
41     {
42         if(x!=0) val+=dfs(now+1,x-1,y,z+1);
43         if(z!=0) val+=dfs(now+1,x+1,y,z-1);
44         else val+=dfs(now+1,x+1,y+1,z);
45     }
46     return val;
47 }
48 signed main()
49 {
50     t=read();
51     dwn(i,t,1)
52     {
53         memset(dp,-1,sizeof(dp));
54         cin>>a+1;
55         len=strlen(a+1);
56         write(dfs(1,0,0,0));
57         putchar('\n');
58     }
59     return 0;
60 }

如有失误请各位大佬斧正（反正我不认识斧正是什么意思）