Cod sursa(job #647671)

Utilizator DEYDEY2Tudorica Andrei DEYDEY2 Data 11 decembrie 2011 19:02:27
Problema PalM Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
#include <cstring>
using namespace std;

int N, i, j, k, p, best;
char S[501];
short int L[501][501][28];

int max(int a, int b) 
{ 
	return a>b?a:b; 
}

int main()
{
    ifstream f("palm.in");
	ofstream g("palm.out");
    f>>s;
    N = strlen(S);
    
    for (i=0; i<N; ++i)
    {
        L[i][i][S[i]-'a'] = 1;
        for (k=26; k>=0; --k)
            L[i][i][k] = max(L[i][i][k], L[i][i][k+1]);
    }
        
    best = 1;
    for (p=1; p<N; ++p)
        for (i=0; i+p<N; ++i)
        {
            j = i+p;
            for (k=26; k>=0; --k)
            {
                L[i][j][k] = L[i][j][k+1];
                L[i][j][k] = max( L[i][j][k], max(L[i+1][j][k], L[i][j-1][k]) );
                if (S[i] == S[j] && S[i]-'a' == k) L[i][j][k] = max( L[i][j][k], L[i+1][j-1][S[i]-'a'] + 2 );
                best = max(best, L[i][j][k]);
            }            
        }
    
    g<<best;
 
    return 0;
}