Cod sursa(job #1075062)

Utilizator andreiiiiPopa Andrei andreiiii Data 8 ianuarie 2014 16:03:51
Problema PalM Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N=505;

char a[N];
int b[N][N][26];

int main()
{
    freopen("palm.in", "r", stdin);
    freopen("palm.out", "w", stdout);
    int n, i, j, k, sol=0;
    fgets(a+1, 505, stdin);
    n=strlen(a+1)-1;
    for(i=1;i<=n;i++)
    {
        for(j=n;j>=i;j--)
        {
            for(k=0;k<26;k++)
            {
                if(b[i][j+1][k]>b[i-1][j][k]) b[i][j][k]=b[i][j+1][k];
                else b[i][j][k]=b[i-1][j][k];
                if(b[i][j][k]<b[i][j][k-1]) b[i][j][k]=b[i][j][k-1];
                if(a[i]==a[j]&&a[i]-'a'==k&&b[i][j][k]<b[i-1][j+1][k]+1) b[i][j][k]=b[i-1][j+1][k]+1;
            }
        }
    }
    for(i=1;i<=n;i++) sol=max(max(b[i][i][25]*2-1, b[i][i+1][25]*2), sol);
    printf("%d", sol);
}