BRACKET - Dãy ngoặc
Tác giả: hieult
Ngôn ngữ: C++
#include <cstdio>
#include <cstring>
//#include <conio.h>
#include <iostream>
long long n,k,a[62],m;
long long f[62][62],g[62][62];
char s[62];
using namespace std;
int main()
{
//freopen("BRACKET.in","r",stdin);
scanf("%lld %lld",&n,&k);
// printf("%d %d\n",'(',')');
scanf("%s",s);
a[0] = 0;
int t = 0;
for(int i = 0;i<n;i++)
{
t++;
if(s[i]=='(') a[t] = a[t-1]+1;
else if(s[i]=')') a[t] = a[t-1]-1;
}
memset(f,0,sizeof(f));memset(g,0,sizeof(g));
f[n][0] = 1;
g[n][0] = 1;
for(int i = n-1;i>=0;i--)
{
f[i][0] = f[i+1][1];
for(int j = 1;j<=k;j++)
f[i][j] = f[i+1][j-1]+f[i+1][j+1];
//printf("%d\n",f[i][0]);
}
for(int i = n-1;i>=0;i--)
{
g[i][0] = g[i+1][1];
for(int j = 1;j<=k-1;j++)
g[i][j] = g[i+1][j-1]+g[i+1][j+1];
// printf("%d\n",g[i][0]);
}
printf("%lld\n",f[0][0]-g[0][0]);
long long kq = 1,kq1=0;
for( t=0;t<=n-1;t++)
{
if(a[t+1]<a[t] && a[t]<k)
kq1 += f[t+1][a[t]+1]-g[t+1][a[t]+1];
if(a[t]==k)
break;
}
for( ;t<=n-1;t++)
if(a[t+1]<a[t] && a[t]<k)
kq1 += f[t+1][a[t]+1];
//printf("%lld %lld %lld\n",f[0][0],g[0][0],kq);
printf("%lld",kq1+1);
// getch();
}