Cod sursa(job #637460)

Utilizator PlayLikeNeverB4George Marcus PlayLikeNeverB4 Data 20 noiembrie 2011 14:34:07
Problema PalM Scor 90
Compilator cpp Status done
Runda .com 2011 Marime 0.83 kb
#include <cstdio>
#include <string>
#include <algorithm>
#include <fstream>
using namespace std;

#define MAXN 512
string S;
int i,len,j,p,q,N,L,Lmax;
int mem[MAXN][MAXN],Ind[MAXN][MAXN];

ifstream fin("palm.in");
ofstream fout("palm.out");

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) {
		if(S[i]<S[a-1]) continue;
		if(R==0) R=1;
		j=Ind[i][b];
		if(j<=i) continue;
		R=max(R,2+caut(i+1,j-1));
	}
	return mem[a][b]=R;
}


int main() {
	fin >> S;
	N=S.size();
	
	for(i=0;i<N-1;++i) {
		p=0;
		for(j=i+1;j<N;++j) {
			if(S[i]==S[j])
				p=j;
			Ind[i][j]=p;    // <=j
			
			mem[i][j]=-1;
		}
	}
	
	Lmax=1;
	for(i=0;i<N-1;++i) {
		j=Ind[i][N-1];
		if(j<=i) continue;
		L=2+caut(i+1,j-1);
		Lmax=max(Lmax,L);
	}
	
	fout << Lmax;
}