Cod sursa(job #635347)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 19 noiembrie 2011 10:39:44
Problema PalM Scor 30
Compilator cpp Status done
Runda .com 2011 Marime 1.04 kb
#include<fstream>
#include<cstring>
#include<vector>
#include<cmath>
using namespace std;
char s[510];
int n,A[510],lis[510],poz[510],lgmax;
vector <int> v[33];

void Citire()
{
	int i;
	ifstream fin("palm.in");
	fin>>s;
	fin.close();
	n=strlen(s);
	for(i=0;i<n;i++)
	{
		A[i+1]=s[i]-'a'+1;
		v[A[i+1]].push_back(i+1);
	}
}

void Rezolvare()
{
	int i,j,pozmax,gasit;
	for(i=1;i<=n;i++)
	{
		pozmax=i;
		for(j=1;j<i;j++)
		{
			if(A[j]<=A[i] && lis[j]>lis[pozmax] && poz[j]>i)
			{
				pozmax=j;
			}
		}
		lis[i]=lis[pozmax]+1;
		gasit=0;
		if(pozmax==i)
			gasit=v[A[i]][v[A[i]].size()-1];
		else
		{
			for(j=v[A[i]].size()-1;j>=0 && !gasit;j--)
			{
				if(v[A[i]][j]<poz[pozmax])
					gasit=v[A[i]][j];
			}
		}
		poz[i]=gasit;
	}
	for(i=1;i<=n;i++)
	{
		if(poz[i]==i)
			lgmax=max(lgmax,2*lis[i]-1);
		else
			lgmax=max(lgmax,2*lis[i]);
	}
}

void Afisare()
{
	ofstream fout("palm.out");
	fout<<lgmax<<"\n";
	fout.close();
}

int main()
{
	Citire();
	Rezolvare();
	Afisare();
	return 0;
}