2817.txt

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

Problem Id:2817  User Id:fzk 
Memory:508K  Time:0MS
Language:C++  Result:Accepted

Source 

#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( "%d\n", answer );
	}
	return 0;
}