Editorial for Dãy ngoặc
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
var n,kk:longint; a:array[0..61] of longint; b:array[0..1,0..61,-1..31] of qword; c:array[0..61,-1..31] of qword; res,re:qword; procedure rf; var i,t:longint; c:char; begin readln(n,kk); t:=0; for i:=1 to n do begin read(c); if c='(' then inc(t) else dec(t); a[i]:=t; end; end; procedure calc(z:longint); var i,j,t,k:longint; begin b[z,0,0]:=1; k:=kk-z; if k<1 then exit; for i:=1 to n div 2 do begin for j:=0 to i do begin if j<k then t:=j else t:=k; b[z,i,t]:=b[z,i-1,t-1]+b[z,i-1,t+1]; end; end; for i:=n div 2 + 1 to n do begin for j:=0 to n-i do begin if j<k then t:=j else t:=k; b[z,i,t]:=b[z,i-1,t-1]+b[z,i-1,t+1]; end; end; end; procedure pr; var i,j,k:longint; kt:boolean; begin fillchar(b,sizeof(b),0); calc(1); calc(0); for i:=0 to n do for j:=0 to kk do c[i,j]:=b[0,i,j]-b[1,i,j]; re:=c[n,0]; k:=1; res:=0; kt:=false; for i:=n-2 downto 2 do begin j:=a[n-i]; if j>k then begin if not kt then res:=res+c[i,k-1] else res:=res+b[0,i,k-1]; end; if j=kk then kt:=true; k:=j; end; end; procedure wf; begin writeln(re); writeln(re-res); end; begin rf; pr; wf; end.
Code mẫu của happyboy99x
#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; }
Code mẫu của ladpro98
#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; }
Code mẫu của RR
const fi=''; fo=''; maxn=61; type mang=array[0..maxn,-1..maxn] of int64; var f:text; n,k,i,j,l,t:longint; sl1,sl2:mang; s:string; res1,res2:int64; procedure doc; begin assign(f,fi); reset(f); readln(f,n,k); readln(f,s); close(f); end; function min(a,b:longint):longint; begin if a<b then exit(a) else exit(b); end; procedure tinh(b:longint;var sl:mang); var i,j:longint; begin sl[0,0]:=1; for i:=1 to n do for j:=0 to b do sl[i,j]:=sl[i-1,j-1]+sl[i-1,j+1]; end; procedure xuli1; begin tinh(k,sl1);tinh(k-1,sl2); res1:=sl1[n,0]-sl2[n,0]; end; procedure xuli2; begin t:=0; for i:=1 to n do begin if s[i]='(' then inc(t) else dec(t); if s[i]=')' then res2:=res2+sl1[n-i,t+2]; end; for i:=1 to n do begin if s[i]='(' then inc(t) else dec(t); if t=k then break; if s[i]=')' then res2:=res2-sl2[n-i,t+2]; end; end; procedure ghi; begin assign(f,fo); rewrite(f); writeln(f,res1); writeln(f,res2+1); close(f); end; begin doc; xuli1; xuli2; ghi; end.
Code mẫu của hieult
#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(); }
Comments