NKPALIN - Chuỗi đối xứng
Tác giả: khuc_tuan
Ngôn ngữ: C++
#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;
}