Cod sursa(job #636855)

Utilizator balakraz94abcd efgh balakraz94 Data 20 noiembrie 2011 00:30:23
Problema PalM Scor 20
Compilator cpp Status done
Runda .com 2011 Marime 1.06 kb
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#define infile "palm.in"
#define outfile "palm.out"
#define n_max 505
#define max(x,y) x>y ? x : y
using namespace std;

char s[n_max];

int a[n_max][n_max];

int n, sol=1;

void citeste()
{
	freopen(infile,"r",stdin);
	
	gets(s+1);
	
	for(;s[n+1];n++);
	
	fclose(stdin);
}


int palm(int ii, int jj)
{
	int ok = 0;
	
	for(int i=ii; i<jj; i++)
		if(!ok && s[i] > s[i+1])
			ok = 1;
		else if(ok && s[i] < s[i+1])
			return 0;

	return a[ii][jj];
}


void rezolva()
{
	for(int i=1;i<=n;i++)
		a[i][i] = 1;
	
	
	for(int k=2;k<=n;k++)
		for(int i=1;i<=n-k+1;i++)
		{
			int j = i + k - 1;
			if(s[i] == s[j])
			{
				if(j>i+1)
				{
					if(a[i+1][j-1])
						a[i][j]+=a[i+1][j-1];
					else
						break;
				}
				a[i][j]+=2;
			}
			sol = max( palm(i,j), sol);
		}
}




void afiseaza()
{
	freopen(outfile,"w",stdout);
	
	printf("%d\n",sol);
	
	fclose(stdout);
}


int main()
{
	citeste();
	rezolva();
	afiseaza();
	
	return 0;
}