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;
}