Cod sursa(job #639745)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 23 noiembrie 2011 21:44:36
Problema PalM Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include<stdio.h>
#include<cstring>

FILE*f=fopen("palm.in","r");
FILE*g=fopen("palm.out","w");

int n,i,j,k,best,local_max;
int D[505],aib[505][30];
char sir[505];

inline int lsb ( int x ){
	return x & -x;
}

inline void update_aib2D ( int x , int y , int val ){
	if ( !x || !y )	return ;
	
	for ( int i = x ; i <= n ; i += lsb(i) ){
		for ( int j = y ; j <= 26 ; j += lsb(j) ){
			if ( aib[i][j] < val )
				aib[i][j] = val;
		}
	}
}

inline int query_aib2D ( int x , int y ){
	if ( !x || !y )	return 0;
	int s = 0;
	
	for ( int i = x ; i > 0 ; i -= lsb(i) ){
		for ( int j = y ; j > 0 ; j -= lsb(j) ){
			if ( s < aib[i][j] )
				s = aib[i][j];
		}
	}
	
	return s;
}

int main () {
	
	fscanf(f,"%s",sir+1);
	
	n = strlen(sir+1);
	
	for ( i = n ; i >= 1 ; --i ){
		for ( j = 1 ; j < i ; ++j ){
			if ( sir[j] <= sir[i] ){
				if ( best < D[j] * 2 + 1 )
					best = D[j] * 2 + 1;
			}
		}
		for ( j = i - 1 ; j ; --j ){
			if ( sir[i] == sir[j] ){
				if ( D[j] < 1 )	{
					D[j] = 1;
					update_aib2D(j,sir[j]-'a'+1,1);
				}
				local_max = 0;
				local_max = query_aib2D(j-1,sir[i]-'a'+1);
				if ( D[j] < local_max + 1 )	{
					D[j] = local_max + 1;
					update_aib2D(j,sir[j]-'a'+1,local_max+1);
				}
			}
		}
	}
	
	for ( i = 1 ; i <= n ; ++i ){
		if ( D[i] * 2 > best )	best = D[i] * 2;
	}
	
	fprintf(g,"%d\n",best);
	
	fclose(f);
	fclose(g);
	
	return 0;
}