COUNTPL - Đếm số Palindrome

Tác giả: ll931110

Ngôn ngữ: C++

#include <cmath>
#include <cstring>
#include <iostream>
#include <string>
using namespace std;

int F[260];
string S;
bool pal[260][260];

int rec(int x)
{
	if (x < 0) return 0;	
	if (F[x] > -1) return F[x];
	
	int best = x;
	for (int i = x; i >= 0; i--) if (pal[i][x]) best = min(best,rec(i - 1));
	return F[x] = 1 + best;
}

int main()
{
//	freopen("pl.in","r",stdin);
//	freopen("pl.ou","w",stdout);
	cin >> S;
	int n = S.size();
	for (int i = 0; i < n; i++) pal[i][i] = true;
	for (int i = 0; i < n - 1; i++) pal[i][i + 1] = (S[i] == S[i + 1]);
	
	for (int len = 3; len <= n; len++)
	  for (int i = 0; i <= n - len; i++)
	  {
		  int j = i + len - 1;
		  pal[i][j] = ((S[i] == S[j]) && pal[i + 1][j - 1]);
	  }
	
	memset(F,-1,sizeof(F));
	printf("%d\n", rec(n - 1));
}

Download