Poj Solution 2511

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

#include <stdio.h>
#include <memory.h>
#include <string.h>
#include <algorithm>
using namespace std;
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 == '' || *q == '' ;
}
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] = '';
        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( "%dn", h+1 );
    printf( "%dn", 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;
}