# Poj Solution 2858

```http://poj.org/problem?id=2858

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

using namespace std;

char w;
char *p;
int pn;

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

struct tile{
char c;
int v;
}tiles;

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

char word;
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;
}
if( t > v ) {
word[m] = '';
sort( word, word+m );
if( std::binary_search( p[m], p[m]+pn[m], &word, cmpw ) )
v = t;
}
}

return v;
}

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

```
This entry was posted in poj. Bookmark the permalink.