Cod sursa(job #638573)

Utilizator swift90Ionut Bogdanescu swift90 Data 20 noiembrie 2011 22:56:01
Problema PalM Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<cstdio>
using namespace std;
char S[510];
int sol[510][510][26],mx[510][510][26];
inline int egal(int a,int b){
	if(S[a]==S[b])
		return 1;
	return 0;
}
inline int maxim(int a,int b){
	return a>b?a:b;
}
int main(){
	freopen("palm.in","r",stdin);
	freopen("palm.out","w",stdout);
	int N,i,j,c,so=0,ax;
	fgets(S+1,1000,stdin);
	for(N=1;'a'<=S[N] && S[N]<='z';)
		++N;
	S[N--]=0;
	
	for(i=1;i<=N;++i){
		for(j=N;j>=i;--j){
			for(c=0;c<26;++c){
				mx[i][j][c]=maxim(mx[i-1][j][c],mx[i][j+1][c]);
				mx[i][j][c]=maxim(mx[i][j][c],mx[i-1][j+1][c]);
			}
			if(S[i]==S[j]){
				ax=0;
				for(c=0;c<=S[i]-'a';++c){
					if(ax<mx[i-1][j+1][c])
						ax=mx[i-1][j+1][c];
				}
				mx[i][j][S[i]-'a']=sol[i][j][S[i]-'a']=ax+1;
				if(i==j){
					if(2*ax+1>so)
						so=2*ax+1;
				}
				else{
					if(2*ax+2>so)
						so=2*ax+2;
				}
			}
		}
	}
	printf("%d\n",so);
	fclose(stdin);
	fclose(stdout);
	return 0;
}