Editorial for Chuỗi đối xứng
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
const maxn=2000; var a,b,kq:array[0..maxn] of char; f:array[0..maxn,0..maxn] of integer; num:integer; procedure rf; begin num:=0; while not eoln do begin inc(num); read(a[num]); end; end; {---------------} procedure pr; var i,j:integer; begin fillchar(f,sizeof(f),0); for i:=1 to num do b[i]:=a[num-i+1]; for i:=1 to num do for j:=1 to num do begin if f[i-1,j]>=f[i,j-1] then f[i,j]:=f[i-1,j] else f[i,j]:=f[i,j-1]; if (a[i]=b[j]) and (f[i,j]<=f[i-1,j-1]) then f[i,j]:=f[i-1,j-1]+1; end; end; {---------------} procedure wf; var i,j,c,pre:integer; begin repeat if a[i]=b[j] then begin write(a[i]); dec(i); dec(j); end else begin if f[i,j]=f[i-1,j] then dec(i) else dec(j); end; until (f[i,j]=0); end; {---------------} begin rf; pr; wf; end.
Code mẫu của happyboy99x
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; #define SZ 2005 #define FOR(i, a, b) for( int i = (a), _b = (b); i <= _b; ++i ) #define max(a, b) ((a) > (b) ? (a) : (b)) char s[SZ]; int f[SZ][SZ], n; void solve() { FOR( len, 1, n ) FOR( i, 0, n-len ) { int j = i + len - 1; if ( len == 1 ) f[i][j] = 1; //else if ( len == 2 ) f[i][j] = s[i] == s[j] ? 2 : max(f[i][j], f[j][j]); else f[i][j] = s[i] == s[j] ? f[i+1][j-1] + 2 : max(f[i][j-1], f[i+1][j]); /*printf( "%d %d %d\n", len, i, j); FOR(i, 0, n-1) { FOR(j, 0, n-1) printf( "%3d", f[i][j] ); putchar('\n'); }*/ } } void print() { char res[SZ]; memset(res, '\0', sizeof res); int i = 0, j = n-1, l = 0; while( i <= j ) { if ( f[i][j] == f[i+1][j] ) ++i; else if ( f[i][j] == f[i][j-1] ) --j; else { res[l++] = s[i]; ++i; --j; } } printf( "%s", res ); if( f[0][n-1] % 2 ) res[--l] = 0; reverse(res, res+l); puts(res); } int main() { scanf( "%s", s ); n = strlen(s); solve(); print(); return 0; }
Code mẫu của ladpro98
program nkpalin;//qhd uses math; const fi=''; var s,res:ansistring; f:array[1..2000,1..2000] of longint; check:array[1..2000,1..2000] of boolean; maxL,dau,cuoi,i,j,kq,len:longint; procedure input; var inp:text; begin assign(inp,fi); reset(inp); readln(inp,s); close(inp); end; function qhd(i,j:longint):longint; begin if (check[i,j]) or (i>j) then exit(f[i,j]); check[i,j]:=true; if s[i]=s[j] then begin f[i,j]:=qhd(i+1,j-1)+2; exit(f[i,j]); end; f[i,j]:=max(qhd(i+1,j),qhd(i,j-1)); exit(f[i,j]); end; procedure init; var i:longint; begin for i:=1 to length(S) do begin check[i,i]:=true; f[i,i]:=1; end; end; begin input; init; for i:=1 to length(s) do for j:=1 to length(s) do qhd(i,j); kq:=qhd(1,length(s)); len:=high(longint); for i:=1 to length(s) do for j:=i to length(s) do begin if (f[i,j]=kq) and ((j-i+1)<len) then begin dau:=i; cuoi:=j; len:=j-i+1; end; end; i:=dau; j:=cuoi; res:=''; while (kq>1) do begin if s[i]=s[j] then begin res:=res+s[i]; dec(kq,2); inc(i); dec(j); end else if f[i+1,j]<f[i,j-1] then begin dec(j); end else inc(i); end; if kq=1 then begin res:=res+s[i]; for i:=length(res)-1 downto 1 do res:=res+res[i]; end else begin for i:=length(res) downto 1 do res:=res+res[i]; end; write(res); end.
Code mẫu của RR
uses math; const MAXN = 2011; var s : ansistring; n : longint; f : array[1..MAXN,1..MAXN] of longint; procedure init; var k,i,j:longint; begin for i:=1 to n do f[i,i]:=1; for k:=1 to n-1 do for i:=1 to n-k do begin j:=i+k; if s[i]=s[j] then f[i,j]:=f[i+1,j-1]+2 else f[i,j]:=max(f[i+1,j],f[i,j-1]); end; end; procedure solve(l,r:longint); begin if l>r then exit; if s[l]=s[r] then begin write(s[l]); solve(l+1,r-1); if l<>r then write(s[r]); end else if f[l+1,r]>f[l,r-1] then solve(l+1,r) else solve(l,r-1); end; begin readln(s); n:=length(s); init; solve(1,n); end.
Code mẫu của hieult
#include <stdio.h> //#include <conio.h> #include <string.h> main() { char s[2000],B[2000]; int f[2000][2000],max[2000][2000],min[2000][2000]; gets(s); int n=strlen(s)-1; f[0][0]=1; min[0][0]=0; max[0][0]=0; for(int i=1;i<=n;i++) { f[i][i]=1; f[i][i-1]=0; max[i][i]=i; min[i][i]=i; } for(int i=1;i<=n;i++) for(int j=0;j<=n-i;j++) { if(s[j]==s[j+i]) { f[j][j+i]=f[j+1][j+i-1]+2; max[j][j+i]=j+i; min[j][j+i]=j; } else { if(f[j+1][j+i]>f[j][j+i-1]) { f[j][j+i]=f[j+1][j+i]; max[j][j+i]=max[j+1][j+i]; min[j][j+i]=min[j+1][j+i]; } else { f[j][j+i]=f[j][j+i-1]; max[j][j+i]=max[j][j+i-1]; min[j][j+i]=min[j][j+i-1]; } } } int x=0,y=n,z=f[0][n],t=f[0][n]; // printf("%d %d %d\n",min[0][n],max[0][n],t); while(z!=0 && z!=1) { B[(t-z)/2+1]=s[min[x][y]]; B[(t+z)/2]=s[max[x][y]]; int xx=x; x=min[x][y]+1; y=max[xx][y]-1; z=z-2; // printf("%d %d\n",x,y); } if(z==1) B[(t+1)/2]=s[min[x][y]]; for(int i=1;i<=t;i++) printf("%c",B[i]); // getch(); }
Code mẫu của ll931110
Program NKPALIN; Const input = ''; output = ''; Var s: array[1..2000] of char; F: array[0..2000,0..2000] of integer; fo: text; n: integer; Procedure init; Var fi: text; Begin Assign(fi, input); Reset(fi); n:= 0; While not eoln(fi) do Begin inc(n); read(fi, s[n]); End; End; Function max(p,q: integer): integer; Begin If p < q then max:= q else max:= p; End; Procedure optimize; Var i,j: integer; Begin Fillchar(F, sizeof(F), 0); For i:= 1 to n do F[i,i]:= 1; For i:= n downto 1 do For j:= i + 1 to n do If s[i] = s[j] then F[i,j]:= F[i + 1,j - 1] + 2 else F[i,j]:= max(F[i + 1,j], F[i,j - 1]); End; Procedure trace(x,y: integer); Begin If x = y then write(fo, s[x]) else if x < y then Begin If s[x] = s[y] then Begin write(fo, s[x]); trace(x + 1,y - 1); write(fo, s[x]); End else if F[x + 1,y] > F[x,y - 1] then trace(x + 1,y) else trace(x,y - 1); End; End; Begin init; optimize; Assign(fo, output); Rewrite(fo); trace(1,n); Close(fo); End.
Code mẫu của skyvn97
#include<stdio.h> #include<string.h> #define MAX 2222 char s[MAX]; bool t[MAX]; int o[MAX][MAX]; int l; int max(int x,int y) { if (x>y) return (x);else return (y); } void count(int i,int j) { if (i>j) return; if (o[i][j]!=0) return; if (i==j) { o[i][j]=1; return; } if (s[i-1]==s[j-1]) { if (j-i==1) { o[i][j]=2; return; } if (o[i+1][j-1]==0) count(i+1,j-1); o[i][j]=o[i+1][j-1]+2; } else { if (o[i+1][j]==0) count(i+1,j); if (o[i][j-1]==0) count(i,j-1); o[i][j]=max(o[i+1][j],o[i][j-1]); } return; } void init(void) { int i; gets(s); l=strlen(s); for (i=1;i<=l;i=i+1) t[i]=false; } void optimize(void) { int i,j; for (i=1;i<l;i=i+1) for (j=i+1;j<=l;j=j+1) count(i,j); } void trace(void) { int i,j; i=1;j=l; while (i<=j) { if (s[i-1]==s[j-1]) { t[i]=true; t[j]=true; i=i+1; j=j-1; } else { if (o[i][j]==o[i+1][j]) i=i+1; else j=j-1; } } for (i=1;i<=l;i=i+1) if (t[i]) printf("%c",s[i-1]); } int main(void) { init(); optimize(); trace(); }
Code mẫu của khuc_tuan
#include <iostream> using namespace std; char a[2020]; int f[2020][2020]; int n; int calc(int i,int j) { if(i>j) return 0; if(i==j) return 1; int &ret = f[i][j]; if(ret!=-1) return ret; ret = 0; ret >?= calc(i+1,j); ret >?= calc(i,j-1); if(a[i]==a[j]) ret >?= calc(i+1,j-1) + 2; return ret; } void truy(int i,int j) { if(i>j) return; if(i==j) { cout << a[i]; return; } int r = f[i][j]; if(r==calc(i+1,j)) { truy(i+1,j); return; } if(r==calc(i,j-1)) { truy(i,j-1); return; } if(a[i]==a[j] && r==calc(i+1,j-1)+2) { cout << a[i]; truy(i+1,j-1); cout << a[j]; return; } } int main() { gets(a); n = strlen(a); memset( f, -1, sizeof(f)); calc(0,n-1); truy(0,n-1); cout << endl; return 0; }
Comments
This comment is hidden due to too much negative feedback. Show it anyway.