Cerința

Ion a învățat la informatica despre cuvintele PALINDROM. Un cuvânt se numeşte PALINDROM dacă citit de la stânga la dreapta și de la dreapta la stânga este același.

Dându-se un cuvânt format din litere mari și mici ale alfabetului englez și cifre, să se afle numărul minim de caractere care pot fi inserate în cuvânt pentru a deveni PALINDROM. Caracterele pot fi inserate oriunde în cuvânt.

Date de intrare

Fișierul de intrare palin.in conține pe prima linie numărul n, iar pe a doua linie cuvântul.

Date de ieșire

Fișierul de ieșire palin.out va conține pe prima linie numărul cerut.

Restricții și precizări

• 1 ≤ n ≤ 4000

Exemplu

palin.in

4
AnA1

palin.out

1

Explicație

Pentru ca cuvântul AnA1 să devină PALINDROM, trebuie adăugat la începutul cuvântului caracterul 1. Cuvântul format, 1AnA1, este PALINDROM.

#include <bits/stdc++.h>
using namespace std;

ifstream cin("palin.in");
ofstream cout("palin.out");

int n , d[4001][4001];
char s[4001] , in[4001];

int main()
{
    cin >> n;
    for(int i = 0 ; i < n ; i++)
        cin >> s[i];

    for(int i = n - 1 ; i >= 0 ; i--)
        in[i] = s[n - i - 1];

    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= n ; j++)
            if(s[i - 1] == in[j - 1]) d[i][j] = d[i - 1][j - 1] + 1;
            else d[i][j] = max(d[i - 1][j] , d[i][j - 1]);

    cout << n - d[n][n];
}