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

Download