2858.txt

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

Problem Id:2858  User Id:fzk 
Memory:872K  Time:171MS
Language:C++  Result:Accepted

Source 

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

char w[100100][11];
char *p[11][100100];
int pn[11];

bool cmpw( char *a, char *b ) {
	return strcmp( a, b ) < 0;
}

struct tile{
	char c[2];
	int v;
}tiles[10];

bool cmp( tile a, tile b ) {
	return a.v < b.v;
}

char word[1000];
int n, ph;

void input( ) {
	int i, l;
	scanf( "%d", &n );
	
	for( i=0; i<=10; i++ )
		pn[i] = 0;

	for( i=0; i<n; i++ ) {
		scanf( "%s", word );
		if( (l=strlen(word)) > 10 ) {
			i--, n--;
			continue;
		}
		sort( word, word+l );
		strcpy( w[i], word );
		p[l][pn[l]++] = w[i];
	}

	for( i=0; i<=10; i++ )
		sort( p[i], p[i]+pn[i], cmpw );
}

void inputahand( ) {
	int i;
	scanf( "%d", &ph );
	
	for( i=0; i<ph; i++ ) {
		scanf( "%1s %d", tiles[i].c, &tiles[i].v );
	}
	sort( tiles, tiles+ph, cmp );
}

int doahand( ) {
	int i, j, k, v = 0, t, m, best = 0, h, g = ph-1;

	for( i=0; i<ph; i++ )
		best += tiles[i].v;
	
	h = (1<<(ph-1))-1;

	for( i=(1<<ph)-1; i>=1; i-- ) {
		if( v >= best )
			break;
		if( i == h ) {
			best -= tiles[g].v;
			g--;
			h = (1<<(g-1))-1;
		}
		
		k = i, t = 0, m = 0;
		for( j=0; k; k>>=1, j++ )
			if( k&1 ) {
				t += tiles[j].v;
				word[m++] = tiles[j].c[0];
			}
		if( t > v ) {
			word[m] = '\0';
			sort( word, word+m );
			if( std::binary_search( p[m], p[m]+pn[m], &word[0], cmpw ) )
				v = t;
		}
	}

	return v;
}

int main( ) {
	input( );
	int m;
	scanf( "%d", &m );
	while( m-- ) {
		inputahand( );
		printf( "%d\n", doahand( ) );
	}
	return 0;
}