Cod sursa(job #637396)

Utilizator FlorianFlorian Marcu Florian Data 20 noiembrie 2011 14:15:28
Problema PalM Scor 0
Compilator cpp Status done
Runda .com 2011 Marime 0.77 kb
using namespace std;
#include<fstream>
const int MAX_N = 157;
int dp[MAX_N][MAX_N][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, j, k;
	for(i = 1; i <= N; ++i) dp[i][i][i] = 1; 
	for(lg = 2; lg <= N; ++lg)
		for(i = 1; i + lg - 1 <= N; ++i)
		{
			j = i + lg - 1;
			for(k = i; k <= j; ++k)
			{
				dp[i][j][k] = dp[i+1][j-1][k];
				if(s[i-1] == s[j-1] && s[i-1] <= s[k-1])
					dp[i][j][k] = 2 + dp[i+1][j-1][k];
				if(dp[i][j][k] < dp[i+1][j][k] ) dp[i][j][k] = dp[i+1][j][k];
				if(dp[i][j][k] < dp[i][j-1][k]) dp[i][j][k] = dp[i][j-1][k];
			}
		}
	int sol;
	for(k = 1; k <= N; ++k)
		if(sol < dp[1][N][k]) sol = dp[1][N][k];
	out << sol << "\n";
	return 0;
}