Poj Solution 2858

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

#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] = '';
            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( "%dn", doahand( ) );
    }
    return 0;
}