Cod sursa(job #637093)

Utilizator PlayLikeNeverB4George Marcus PlayLikeNeverB4 Data 20 noiembrie 2011 11:51:33
Problema PalM Scor 70
Compilator cpp Status done
Runda .com 2011 Marime 0.81 kb
#include <cstdio>
#include <string.h>
#include <algorithm>
#include <stdlib.h>
using namespace std;

#define MAXN 512
char S[MAXN];
int i,j,N,L,Lmax;
int mem[MAXN][MAXN];

int caut(int a, int b) {
	if(a>b) return 0;
	if(a==b && S[a]>=S[a-1]) return 1;
	if(mem[a][b]>=0) return mem[a][b];
	
	int i,j,R=0;
	for(i=a;i<b;i++) {
		for(j=i+1;j<=b;j++)
			if(S[i]==S[j] && S[i]>=S[a-1])
				R=max(R,2+caut(i+1,j-1));
		if(S[i]>=S[a-1])
			R=max(R,1);
	}
	return mem[a][b]=R;
}

int main() {
	freopen("palm.in","r",stdin);
	freopen("palm.out","w",stdout);
	
	scanf("%s",&S);
	N=strlen(S);
	
	for(i=0;i<N;i++)
		for(j=i;j<N;j++)
			mem[i][j]=-1;
	
	for(i=0;i<N-1;i++)
		for(j=i+1;j<N;j++) {
			if(S[i]!=S[j]) continue;
			L=2+caut(i+1,j-1);
			Lmax=max(Lmax,L);
		}
	printf("%d",Lmax);
}