Cod sursa(job #2181889)

Utilizator NToniBoSSNicolae Tonitza NToniBoSS Data 21 martie 2018 21:44:17
Problema PalM Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <cstdio>
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;
char v[505];
int a[505][505];
int main()
{
    int n,rez,i,j,l;
    char c;
    ifstream in("palm.in");
    ofstream out("palm.out");
    in>>v;
    n=strlen(v)-1;
    for(c='z'; c>='a'; c--)
    {
        for(i=0; i<=n; i++)
            if(v[i]==c)
                a[i][i]=1;
        for(i=0; i<n; i++)
            if(v[i]==v[i+1] && v[i]==c)
                a[i][i+1]=2;
        for(l=1; l<=n; l++)
            for(i=0; i+l<=n; i++)
            {
                j=i+l;
                if(v[i]==v[j] && v[i]==c)
                    a[i][j]=max(a[i][j],a[i+1][j-1]+2);
                a[i][j]=max(a[i][j],a[i+1][j]);
                a[i][j]=max(a[i][j],a[i][j-1]);
            }
    }
    out<<a[0][n];

    return 0;
}