Cod sursa(job #639006)

Utilizator paul_gabryelPaul Buda paul_gabryel Data 22 noiembrie 2011 08:50:38
Problema PalM Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb

#include <fstream>
#include <cstdio>
#include <algorithm>
#include <string>

using namespace std;

int sol,bst[512][512][32],n;
string s;

void read ()
{
	ifstream in ("palm.in");
	in>>s;
}

void solve ()
{
	n=s.size();
	--n;
	for(int i=0;i<=n;++i)
		bst[i][i][s[i]-'a']=1;
	for(int i=n-1;i>=0;--i)
		for(int j=i+1;j<=n;++j)
			if(s[i]==s[j])
				for(int k=s[i]-'a';k<26;++k)
					bst[i][j][s[i]-'a']=max(bst[i][j][s[i]-'a'],bst[i+1][j-1][k]+2);
			else
				for(int k=0;k<26;++k)
					bst[i][j][k]=max(bst[i+1][j][k],bst[i][j-1][k]);
	for(int i=0;i<26;++i)
		if(bst[0][n][i]>sol)
			sol=bst[0][n][i];
}

void out ()
{
	freopen ("palm.out","w",stdout);
	printf("%d",sol);
}

int main ()
{
	read ();
	solve ();
	out ();
	return 0;
}