3192.txt

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

Source

Problem Id:3192  User Id:fzk 
Memory:64K  Time:30MS
Language:C++  Result:Accepted

Source 

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

using namespace std;

int index[7];
char sum[100];
char str[7][10];
int len[7];

int merge( int len, char *w, int l ) {
	int i = len-l, j;
	if( i<0 ) i = 0;

	for( ; i<=len; i++ ) {
		for( j=0; sum[i+j] && w[j] == sum[i+j]; j++ )
			;
		if( sum[i+j] == 0 ) {
			for( ;j<l; j++ )
				sum[i+j] = w[j];
			return i+l;
		}
	}
	
	return -1; // never execute
}

int main( ) {
	int n, i, l, ans = 1000;
	scanf( "%d", &n );
	for( i=0; i<n; i++ ) {
		scanf( "%s", str[i] );
		len[i] = strlen( str[i] );
		index[i] = i;
	}

	do {
		l = 0;
		for( i=0; i<n; i++ ) {
			sum[l] = '\0';
			l = merge( l, str[ index[i] ], len[ index[i] ] );
		}

		if( l < ans )
			ans = l;
	}while( std::next_permutation( index, index+n ) );

	printf( "%d\n", ans );

	return 0;
}