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

Download