BRACKET - Dãy ngoặc

Tác giả: happyboy99x

Ngôn ngữ: C++

#include<cstdio>

const int N = 60 + 2;
long long f[N][N/2][2];
int n, k;
char s[N];

void dp() {
	f[n][0][0] = 1;
	for(int x = n; x > 0; --x)
		for(int y = k; y >= 0; --y)
			for(int c = 0; c <= 1; ++c) {
				if(y > 0) f[x-1][y-1][c] += f[x][y][c];
				if(y < k) f[x-1][y+1][(y+1==k)|c] += f[x][y][c];
			}
}

long long order(char * s) {
	long long res = 1;
	int preH = 0, h = 0;
	bool c = false;
	for(int i = 0; i < n; ++i) {
		h += s[i] == '(' ? 1 : -1;
		if(h < preH && h + 2 <= k) {
			res += f[i+1][h+2][1];
			if(c) res += f[i+1][h+2][0];
		}
		c |= h == k; preH = h;
	}
	return res;
}

int main() {
	scanf("%d%d%s", &n, &k, s);
	dp();
	printf("%lld\n%lld\n", f[0][0][1], order(s));
	return 0;
}

Download