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

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.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Palin:

///Moca Andrei - solutie 100p
#include <fstream>
using namespace std;
#define dim 4002
int n, L[dim][dim];
char A[dim], B[dim], s[dim];
void SCMaximal()
{
    ifstream cin("palin.in");
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> s[i];
    for (int i = 1; i <= n; i++)
    {
        A[i] = s[i];
        B[i] = s[n - i + 1];
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (A[i] == B[j])
                L[i][j] = L[i-1][j-1] + 1;
            else
                L[i][j] = max(L[i-1][j], L[i][j-1]);

    ofstream cout("palin.out");
    cout << n - L[n][n];
}
int main()
{
    SCMaximal();
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1872 Palin

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1872 Palin de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1872 Palin