Cod sursa(job #634525)

Utilizator cezar305Mr. Noname cezar305 Data 16 noiembrie 2011 17:04:48
Problema PalM Scor Ascuns
Compilator cpp Status done
Runda Marime 0.64 kb
//eudanip
#include<stdio.h>
#include<string.h>

#define NMAX 504
#define maxim(a,b) (a>b ? a : b)

int d[NMAX][NMAX][31];
int sol,nr;
char s[1005];

int main ()
{
	int i,j,k;

	freopen("palm.in","r",stdin);
	freopen("palm.out","w",stdout);
	scanf("%s",s);
	nr=strlen(s);
	for(i=nr;i>=1;i--)
		s[i]=s[i-1];
	for(i=1;i<=nr;i++)
		for(j=nr;j>=i;j--)
			for(k=1;k<=26;k++)
			{
				d[i][j][k]=maxim(d[i-1][j][k],d[i][j+1][k]);
				if(s[i]==s[j] && s[i]-'a'+1==k)
					d[i][j][k]=maxim(d[i][j][k],d[i-1][j+1][k]+1);
				d[i][j][k]=maxim(d[i][j][k],d[i][j][k-1]);
			}	
	for(i=1;i<=nr;i++)
		sol=maxim(sol,d[i][i][26]);
	printf("%d\n",2*sol-1);
	return 0;
}