Cod sursa(job #639488)

Utilizator stay_awake77Cangea Catalina stay_awake77 Data 23 noiembrie 2011 12:49:30
Problema PalM Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <cstdio>
#include <cstring>

#define NMAX 505
#define ALFA 26

char S[NMAX];
int i, j, k, D[NMAX][NMAX][ALFA], N, Rez;

inline int MAX( int x, int y )
{
	return ( x > y ) ? x : y;
}

int main()
{
	freopen("palm.in", "r", stdin);
	freopen("palm.out", "w", stdout);
	
	gets( S+1 );
	N = strlen( S+1 );
	
	for( i = 1; i <= N; ++i )
		for( j = N; j >= i; --j )
			for( k = 0; k < 26; ++k )
			{
				D[i][j][k] = MAX( D[i-1][j][k], D[i][j+1][k] );
				if( S[i] == S[j] && (int)(S[i] - 'a') == k )
					D[i][j][k] = MAX( D[i][j][k], D[i-1][j+1][k] + 1 );
				
				D[i][j][k] = MAX( D[i][j][k], D[i][j][k-1] );
			}
	
	for( i = 1; i <= N; ++i )
		Rez = MAX( Rez, 2*D[i][i][25] - 1 ), Rez = MAX( Rez, 2*D[i][i+1][25] );
	printf("%d\n", Rez);
	
	return 0;
}