1171.txt

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

#include<stdio.h>
#include<hash_map.h>
#include<algorithm>
#include<string.h>
using namespace std;
struct eqstr
{
        bool operator()(char* s1, char* s2) const
        {
                return strcmp(s1, s2) == 0;
        }
};

hash_map<char*, int, hash<char*>, eqstr> s;
typedef hash_map<char*, int, hash<char*>, eqstr>::iterator iter;

char w[40000][8];
char cell[8];
int value[] = { 2,5,4,4,1,6,5,5,1,7,6,3,5,2,3,5,7,2,1,2,4,6,6,7,5,7 };

void add( char *p, int ps ) {
    iter it = s.find( p );
    if( it == s.end() )
        s.insert( make_pair( p, ps ) );
}    

int main( ) {
    char *t, *q, *p, rest[8], *r, temp[8];
    int i, j, l, len, ans = 0, ps, k=0;
    iter it;
    scanf( "%s", cell );
    len = strlen( cell );
    sort( cell, cell+len );
    
    while( 1 ) {
        scanf( "%s", w[k] );
        t = w[k++];
        if( t[0] == '.' )
            break;
        l = strlen(t);
        
        if( l > len )
            continue;
            
        sort( t, t+l );
        q = t, p = cell, r=rest;
        ps = 0;
        while( *q && *p ) {
            if( *q < *p )
                break;
            else if( *q == *p ) {
                ps += value[*p-'a'];
                q++, p++;
            }
            else {
                *r++ = *p++;
            }
        }
        
        if( *q == 0 ) {
            while( *p )
                *r++ = *p++;
            if( ps > ans ) ans = ps;
            
            for( i=1; i<(1<<(len-l)); i++ ) {
                p = temp;
                for( j=0; (1<<j)<=i; j++ )
                    if( i&(1<<j) )
                      *p++ = rest[j];
                *p = '\0';
                
                it = s.find( temp );

                if( it != s.end() && ps + it->second > ans )
                    ans = ps + it->second;
                
            }
            add( t, ps );
        }
        
    }
    
    printf( "%d\n", ans ); 
    scanf( "%s", t );
    return 0;
}