BRACKET - Dãy ngoặc

Tác giả: ladpro98

Ngôn ngữ: C++

#include <bits/stdc++.h>
const int N = 66;
using namespace std;
string s;
long long F[N][N][N], G[N][N][2][N];
int n, d;

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> d; cin >> s;
    G[n][0][0][0] = 1;
    for(int i = n; i; i--)
    for(int j = 0; j <= d; j++)
    for(int k = 0; k <= d; k++)
    if (G[i][j][0][k] || G[i][j][1][k]) {
        F[i][j][k] = G[i][j][0][k] + G[i][j][1][k];
        G[i - 1][j + 1][1][max(k, j + 1)] += F[i][j][k];
        if (j) G[i - 1][j - 1][0][k] += F[i][j][k];
    }
    cout << G[0][0][0][d] << endl;
    int deg = 0; long long res = 1; bool passed = false;
    for(int i = 0; i < n; i++) {
        if (s[i] == ')') {
            if (passed) res += accumulate(G[i][deg][0], G[i][deg][0] + d + 1, 0);
            else
                res += G[i][deg][0][d];
        }
        if (s[i] == '(') deg++; else deg--;
        if (deg == d) passed = true;
    }
    cout << res << endl;
	return 0;
}

Download