2511.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include <stdio.h>
#include <memory.h>
#include <string.h>
#include <algorithm>
char word[2500][100];
char mem[2500][100];
int v[2500];
int e[2500][2500];
int d[2500];
int id[2500];
int ans[2500][10];
int from[2500][10];
int n;
bool cmp( int a, int b )
{
	return strcmp( word[a], word[b] ) > 0;
}
bool check( int a,int b )
{
	char *p = word[a], *q = word[b];
	while( *p && *q && *p != *q )
		p++,q++;
	return *p == '\0' || *q == '\0' ;
}
void init()
{
	int i, j, k;
	scanf( "%d", &n );
	for( i=0; i<n; i++ )
	{
		scanf( "%d", &v[i] );		
		gets( word[i] );
		strcpy( mem[i], word[i] );
		for(j=0, k=0; word[i][j]; j++ )
		{
			if( word[i][j] >= 'A' && word[i][j] <= 'Z' ) word[i][j] += 'a' - 'A';
			
			if( word[i][j] >= 'a' && word[i][j] <= 'z' ) word[i][ k++ ] = word[i][j];
		}
		word[i][k] = '\0';
		id[i] = i;
	}
	std::sort( id, id+n, cmp );
	for( i=0; i<n; i++ )
	{
		d[i] = 0;
		for( j=0; j<i; j++ )
		if( check( id[i], id[j] ) )
			e[i][ d[i]++ ] = j;
	}
	memset( ans, -1, sizeof(ans) );

}
int main()
{
	int i, j, k, h, value;
	init();
	for( i=0; i<n; i++ )
	{
		value = ans[i][0] = v[ id[i] ];
		
		for( j=0; j<d[i]; j++ )
		{
			k = e[i][j];
	
			for( h=0; h<9; h++ )
				if( ans[i][h+1] < 0 || ans[k][h] + value > ans[i][h+1] )
				{
					ans[i][h+1] = ans[k][h] + value;
					from[i][h+1] = k;
				}
		}
	}	
	value = -1;
	for( i=0; i<n; i++ )
	for( j=0; j<10; j++ )
	{
		if( ans[i][j] > value )
		{
			k = i;
			h = j;
			value = ans[i][j];
		}
	}
	printf( "%d\n", h+1 );
	printf( "%d\n", value );
	while( h>=0 )
	{
		for( i=0; mem[id[k]][i] == ' '; i++ );
		for( ;mem[id[k]][i]; i++ )
			printf( "%c", mem[id[k]][i] );		
		printf( "\n" );
		k = from[k][h];
		h--;
	}
	return 0;
}