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