COUNTPL - Đếm số Palindrome

Tác giả: ladpro98

Ngôn ngữ: C++

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <cstring>

#define REP(i, a, b) for(int i = (a); i <= (b); ++i)
#define REPD(i, a, b) for(int i = (a); i >= (b); --i)
#define endl '\n'

const int N = 500;

using namespace std;

bool isPalin[N][N];
int f[N], trace[N];
char s[N];

int main() {
	scanf("%s", s + 1);
	int n = strlen(s + 1);
	REP(i, 1, n) isPalin[i][i] = isPalin[i + 1][i] = 1;
	REPD(i, n, 1) REP(j, i + 1, n)
		isPalin[i][j] = s[i] == s[j] && isPalin[i + 1][j - 1];
	REP(i, 1, n) {
		f[i] = n;
		REPD(j, i, 1)
			if (isPalin[j][i] && f[i] > f[j - 1]) {
				f[i] = f[j - 1] + 1;
				trace[i] = j;
			}
	}
	cout << f[n] << endl;
        /*
	vector<string> ans;
	for (int i = n; i; i = trace[i] - 1) {
		string palin = "";
		REP(j, trace[i], i) palin += s[j];
		ans.push_back(palin);
	}
	reverse(ans.begin(), ans.end());
	for(vector<string>::iterator it = ans.begin(); it != ans.end(); ++it)
		cout << *it << endl;
        */
	return 0;
}

Download