COUNTPL - Đếm số Palindrome
Tác giả: RR
Ngôn ngữ: C++
#include <iostream>
#include <algorithm>
#define FOR(i,a,b) for(int i=a; i<=b; i++)
using namespace std;
int main() {
char s[300];
gets(s);
int n = strlen(s)-1;
int f[300];
bool dx[300][300];
FOR(i,0,n) {
dx[i][i] = true;
if (i) dx[i][i-1] = true;
}
FOR(l,1,n)
FOR(i,0,n-l) {
int j = i + l;
dx[i][j] = dx[i+1][j-1] & (s[i] == s[j]);
}
FOR(i,0,n) {
if (dx[0][i]) f[i] = 1;
else f[i] = n+10;
FOR(j,0,i-1)
if (dx[j+1][i])
f[i] = min(f[i], f[j]+1);
}
printf("%d",f[n]);
return 0;
}