Poj Solution 2817

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

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


int ans[12][1024][10];

int link[10][10];
int len[10];

char w[10][20];

int join_num( int i, int j ) {
    int k, l, ans = 0, h;
    for( k=0; w[i][k]; k++ ) {
        for( l=0, h=0; w[i][k+l] && w[j][l]; l++ )
            h += ( w[i][k+l] == w[j][l] );
        if( ans < h )
            ans = h;
    }
    for( k=0; w[j][k]; k++ ) {
        for( l=0, h=0; w[j][k+l] && w[i][l]; l++ )
            h += ( w[j][k+l] == w[i][l] );
        if( ans < h )
            ans = h;
    }
    return ans;
}


int main( ) {
    int n, i, j, k, m, l, answer, t;
    while( 1 ) {
        scanf( "%d", &n );
        if( n <= 0 )
            break;

        for( i=0; i<n; i++ ) {
            scanf( "%s", w[i] );
            len[i] = strlen( w[i] );
        }

        k = 0;
        for( j=0; j<n; j++ )
        for( i=j+1; i<n; i++ )
            link[i][j] = link[j][i] = join_num( i, j );
        
        memset( ans, -1, sizeof ans );
        
        for( i=0; i<n; i++ )
            ans[1][1<<i][i] = 0;
        m = (1<<n);
        
        answer = 10000;
        
        for( i=1; i<n; i++ )
        for( j=0; j<m; j++ )
        for( k=0; k<n; k++ )
        {
            if( ans[i][j][k] >= 0 ) {
                for( l=0; l<n; l++ )
                    if( !( j & (1<<l) ) ) {
                        t = ( j | (1<<l) );
                        if( ans[i+1][t][l] < 0 || 
                            ans[i+1][t][l] < ans[i][j][k]+link[k][l] ){
                                ans[i+1][t][l] = ans[i][j][k]+link[k][l];
                            }
                    }
            }
        }
        answer = 0;
        for( j=0; j<m; j++ )
        for( k=0; k<n; k++ )
        if( ans[n][j][k] > answer )
            answer = ans[n][j][k];
        printf( "%dn", answer );
    }
    return 0;
}