Cod sursa(job #637382)

Utilizator FlorianFlorian Marcu Florian Data 20 noiembrie 2011 14:12:49
Problema PalM Scor 20
Compilator cpp Status done
Runda .com 2011 Marime 0.9 kb
using namespace std;
#include<fstream>
#include<cstring>
const int MAX_N = 505;
short int dp[MAX_N][4][MAX_N];
int N;
char s[MAX_N];
int main()
{
	ifstream in("palm.in"); ofstream out("palm.out");
	in >> s;
	N = strlen(s);
	int lg, i, k, cur = 2, ant = 1, preant = 0;
	for(i = 1; i <= N; ++i) dp[i][ant][i] = 1; 
	for(lg = 2; lg <= N; ++lg)
	{
		for(i = 1; i + lg - 1 <= N; ++i)
		{
			for(k = i; k <= i + lg - 1; ++k)
			{
				dp[i][cur][k] = 0;
				if(s[i-1] == s[i + lg - 2] && s[i-1] <= s[k-1])
					dp[i][cur][k] = 2 + dp[i+1][preant][k];
				if(dp[i][cur][k] < dp[i+1][ant][k]) dp[i][cur][k] = dp[i+1][ant][k];
				if(dp[i][cur][k] < dp[i][ant][k]) dp[i][cur][k] = dp[i][ant][k];
			}
		}
		int aux = preant;
		preant = ant; 
		ant = cur;
		cur = aux;
	}
	short int sol = 1;
	for(k = 1; k <= N; ++k)
		if(sol < dp[1][ant][k]) sol = dp[1][ant][k];
	out << sol << "\n";
	return 0;
}