看了这题一两天后都不知道怎么DP, 昨晚发热(应该不是H1N1)后突然想出如下方法...
首先预处理任意两字符串的最大相同长度
考虑生成所有的排列, 对每一个排列只允许当前字符串最多和前面一个字符串进行重叠, 并且是最大程度重叠.
非严格证明: 如果当前字符串应该和前面一个或者多个进行重叠, 那么在所有的排列中必然有将此字符串放到之前的位置, 也就是这种情况必然会被计算. 
另外如果当前字符串和前面一个字符串部分重叠, 最大程度的重叠与非最大程度的重叠产生的状态是一样的.
主要感觉是一段字符串被覆盖的先后没什么影响. 所以每次的附加代价就为当前字符串长度减去与前一个字符串的最大相同长度.
#include <iostream>
using namespace std;
const int INF = 1<<30;
const int MAXN = 30;
char s[MAXN][MAXN];
int n, w[MAXN][MAXN], len[MAXN];
bool used[MAXN];
int route[MAXN], minlen;

void calsame(int a, int b){
	int i, j, k;
	w[a][b] = 0;
	for(k = len[b]-1; k >= 0; --k){
		for(i = len[a]-k-1, j = 0; i < len[a]; ++i, ++j)
			if(s[a][i] != s[b][j])
				break;
		if(j == k+1){
			w[a][b] = k+1;
			break;
		}
	}	
}

void dfs(int dep, int curlen){
	if(dep == n){
		minlen = min(minlen, curlen);
		return ;
	}
	if(curlen >= minlen)	return ;
	for(int i = 0; i < n; ++i){
		if(used[i])	continue;
		used[i] = true;
		route[dep] = i;
		if(dep == 0)	dfs(dep+1, curlen+len[i]);
		else	dfs(dep+1, curlen+len[i]-w[route[dep-1]][i]);
		used[i] = false;
	}
}

void solve(){
	int i, j, k;
	for(i = 0; i < n; ++i)
		for(j = 0; j < n; ++j){
			calsame(i, j);
		}
	dfs(0, 0);
	printf("%d\n", minlen);
}
	
int main(){
//	freopen("in.txt", "r", stdin);	freopen("out.txt", "w", stdout);
	int T;
	scanf("%d", &T);
	while(T--){
		scanf("%d", &n);
		int i, j;
		for(i = 0; i < n; ++i){
			scanf("%s", s[i]);
			len[i] = strlen(s[i]);
		}
		minlen = INF;
		solve();
	} 
	return 0;
}

• Re:非严格证明的47msAC想法, 谁能证明我的对错? (绝非显摆...) (50) lvhao945 2010-08-21 13:09:19