Cod sursa(job #638291)

Utilizator cosmyoPaunel Cosmin cosmyo Data 20 noiembrie 2011 20:04:49
Problema PalM Scor 20
Compilator cpp Status done
Runda .com 2011 Marime 1.96 kb
#include <fstream>
#include <string>
using namespace std;
string s;
int L[505], D[505], W[505][30], R[505][30], APL[505][30], APD[505][30] ;
inline int max(int a, int b){
	if(a < b)
		return b;
	else
		return a;
}

inline int min(int a, int b){
	if(a < b)
		return a;
	else
		return b;
}

int main(){
	ifstream fin("palm.in");
	ofstream fout("palm.out");
	int i, n, j, k, sw;
	fin >> s;
	n = s.size();
	for(i = 0; i < n; ++i){
		for(j = 0; j < i ; ++j)
			if(s[i] - s[j] <= 1 && L[j] > L[i])
				L[i] = L[j];
		sw = 1;
		for(j = 0;j < i; ++j)
			if(L[i] == L[j] && s[i] - s[j] == 0){
				for(k = 0; k < 26; ++k)
					APL[i][k] = APL[j][k];
				sw = 0;
				break;
			}
		
		if(sw)
		for(j = 0; j < i ; ++j)
			if(L[i] == L[j] && s[i] - s[j] == 1){
				for(k = 0; k < 26; ++k)
					APL[i][k] = APL[j][k];
				break;
			}
		++L[i];
		APL[i][s[i] - 'a']++;
	}

	for(i = n - 1; i >= 0; --i){
		for(j = n - 1; j > i; --j)
			if(s[i] - s[j] <= 1 && D[j] > D[i])
				D[i] = D[j];
		sw = 1;
		for(j = n - 1; j > i; --j)
			if(s[i] - s[j] == 0 && D[j] == D[i]){
				for(k = 0; k < 26; ++k)
					APD[i][k] = APD[j][k];
				sw = 0;
				break;
			}
		if(sw)
		for(j = n - 1; j > i; --j)
			if(s[i] - s[j] == 1 && D[j] == D[i]){
				for(k = 0; k < 26; ++k)
					APD[i][k] = APD[j][k];
				break;
			}
		++D[i];
		APD[i][s[i] - 'a']++;
	}
	
	int MAX = 0;
/*	for(i = 0; i < n; ++i){
		for(j = 0; j <= 'z' - 'a'; ++j)
			if(APD[i][j])
				fout << i << " " << (char)(j + 'a') << " "  << APD[i][j] << '\n';
	}
*/
	for(i = 0; i< n; ++i){
		int rez = 0;
		for(j = 0; j < 26; ++j)
			if(s[i] != (j + 'a'))
				rez += min(APL[i][j], APD[i][j]);
//		fout << i << " " << rez << '\n';
		if((rez + min(APL[i - 1][s[i] - 'a'], APD[i + 1][s[i] - 'a'])) * 2 + 1 > MAX)
			MAX = (rez + min(APL[i - 1][s[i] - 'a'], APD[i + 1][s[i] - 'a'])) * 2 + 1;
		if((rez + min(APL[i][s[i] - 'a'], APD[i + 1][s[i] - 'a'])) * 2 > MAX)
			MAX = (rez + min(APL[i][s[i] - 'a'], APD[i + 1][s[i] - 'a'])) * 2;
	}
			

	fout << MAX << '\n';
	return 0;
}