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();
        
}

Download