Editorial for Đếm số Palindrome

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

uses math;
var s:string;
i,j,n:longint;
f:array[0..255] of longint;
d:array[0..255,0..255] of boolean;

begin
n:=length(s);
for i:=1 to n do d[i,i]:=true;
for i:=1 to n-1 do
if s[i]=s[i+1] then d[i,i+1]:=true;
for j:=3 to n do
for i:=1 to n-j+1 do
d[i,i+j-1]:=d[i+1,i+j-2] and (s[i]=s[i+j-1]);
for i:=1 to n do f[i]:=300;
for i:=1 to n do
for j:=0 to i-1 do
if d[j+1,i] then f[i]:=min(f[i],f[j]+1);
writeln(f[n]);
end.


Code mẫu của happyboy99x

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define sz(a) int((a).size())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); i != _e; ++i)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)

#define INF 1000000000
#define N 260

char s[N]; int f[N][N];

int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
scanf("%s",s); int n = strlen(s);
fo(len,1,n) rep(i,n+1-len) {
int j = i+len-1;
if(len == 1) f[i][j] = 1;
else if(len == 2) f[i][j] = s[i] == s[j] ? 1 : 2;
else if( s[i] == s[j] && f[i+1][j-1] == 1 ) f[i][j] = 1;
else {
f[i][j] = len;
fo(k,i,j-1) f[i][j] = min(f[i][j], f[i][k]+f[k+1][j]);
}
}
printf("%d\n", f[0][n-1]);
return 0;
}


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


Code mẫu của RR

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


Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
#include <string.h>

int main()
{
// freopen("COUNTPL.in","r",stdin);
int f[256];
bool a[256][256];
char s[256];
scanf("%s",s);
int n = strlen(s);
for(int i = 0;i<n;i++)
{
for(int j = 0;j<=n-1-i;j++)
{
if(i==0) a[j][j]= true;
else if(i==1)
{
if(s[j]==s[j+1]) a[j][j+1]=true;
else a[j][j+1]= false;
}
else
{
if(s[j]!=s[j+i]) a[j][j+i]=false;
else  a[j][j+i]=a[j+1][j+i-1];
}
}
}
f[0]=1;
for(int i  = 1;i<=n-1;i++)
{
if(a[0][i]) f[i]=1;
else
{
int min = 1000;
for(int j = 1;j<=i;j++)
if(a[j][i] && f[j-1]+1<min)
min = f[j-1]+1;
f[i]=min;
}
}
printf("%d",f[n-1]);
//getch();
}


Code mẫu của ll931110

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