Cod sursa(job #637335)

Utilizator PlayLikeNeverB4George Marcus PlayLikeNeverB4 Data 20 noiembrie 2011 13:50:42
Problema PalM Scor 90
Compilator cpp Status done
Runda .com 2011 Marime 0.86 kb
#include <cstdio>
#include <string.h>
#include <algorithm>
#include <stdlib.h>
using namespace std;

#define MAXN 512
char S[MAXN];
int i,len,j,p,q,v,N,Lmax;
int dp[MAXN][MAXN],P[MAXN][MAXN];

int main() {
	freopen("palm.in","r",stdin);
	freopen("palm.out","w",stdout);
	
	fgets(S,sizeof(S),stdin);
	N=strlen(S);
	while(S[N-1]<'a' || S[N-1]>'z') N--;
	
	for(i=0;i<N-1;i++)
		for(j=i+1;j<N;j++)
			if(S[i]==S[j])
				P[i][++P[i][0]]=j;
	
	for(len=2;len<=N;len++)
		for(i=0;i<N-len+1;i++) {
			j=i+len-1;
			if(S[i]!=S[j]) continue;
			dp[i][j]=2;
			
			for(p=i+1;p<j;p++) {
				if(S[p]<S[i]) continue;
				dp[i][j]=max(dp[i][j],3); // 2+ 1
				
				for(v=1;v<=P[p][0] && P[p][v]<j;v++);
				v--;
				if(v==0) continue;
				q=P[p][v];
				dp[i][j]=max(dp[i][j],dp[p][q]+2);
			}
			Lmax=max(Lmax,dp[i][j]);
		}
	
	printf("%d",Lmax);
}