Cod sursa(job #637293)

Utilizator Cristy94Buleandra Cristian Cristy94 Data 20 noiembrie 2011 13:40:26
Problema PalM Scor 30
Compilator cpp Status done
Runda .com 2011 Marime 0.85 kb
#include<cstdio>
#include<algorithm>
#include<cstring>
#define Nmax 512
#define Sigma 32
using namespace std;

char s[Nmax];
int a[Nmax][Nmax][Sigma],N;
//lungimea maxima a palindromului sa inceapa pe poz i, sa se termine pe poz j si
//sa aiba literele din margine c

int main(){
	
	freopen("palm.in","r",stdin);
	freopen("palm.out","w",stdout);
	
	fgets(s,Nmax,stdin);
	N=strlen(s);
	
	for(int i=N-1;i>=0;--i)
		for(int j=i;j<N;++j){
			char c=s[j];
			
			if(i==j)
				a[i][j][c]=1;
			else
			//daca litera curenta egala cu prima litera
			if(s[i]==c)
			for(char l=c;l<='z';++l)
				if(a[i+1][j-1][l]!=0 || (i+1)>(j-1))
				a[i][j][c]=max(a[i][j][c],a[i+1][j-1][l]+2);
			
	}
	
	int sol=0;
	for(int i=0;i<N;++i)
		for(int j=i;j<N;++j)
			for(char l='z';l>='a';--l)
				sol=max(sol,a[i][j][l]);
	
	printf("%d",sol);
return 0;
}