Cod sursa(job #2537557)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 3 februarie 2020 19:25:49
Problema PalM Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <bits/stdc++.h>
#define DIM 510
using namespace std;

ifstream fin ("palm.in");
ofstream fout ("palm.out");
int dp[DIM][DIM],_next[DIM][30],_prv[DIM][30];
char v[DIM];
int n,i,j,lg,lit;
int main (){

    fin>>v+1;
    n = strlen (v+1);
    /// dp[i][j] - cel mai lung palindrom dintre pozitiile i,j care e munte in c

    for (i=1;i<=n;i++)
        dp[i][i] = 1;

    for (j=0;j<26;j++){
        for (i=1;i<=n;i++){
            if (v[i]-'a' == j)
                _prv[i][j] = i;
            else _prv[i][j] = _prv[i-1][j];
        }
        for (i=n;i;i--){
            if (v[i]-'a' == j)
                _next[i][j] = i;
            else _next[i][j] = _next[i+1][j];
        }
    }
    int sol = 0;
    for (lg=1;lg<=n;lg++){
        for (i=1;i+lg<=n;i++){
            j = i + lg;

            if (v[i] != v[j])
                dp[i][j] = 0;

            dp[i][j] = 2;
            for (lit=v[i]-'a';lit<26;lit++){
                int poz1 = _next[i+1][lit];
                int poz2 = _prv[j-1][lit];
                if (poz1 <= poz2)
                    dp[i][j] = max (dp[i][j],dp[poz1][poz2]+2);
            }
            sol = max (sol,dp[i][j]);
        }}


    fout<<sol;



    return 0;
}