題意：給定一些DNA序列，求一個最短序列能夠包含所有序列。

      思路：記錄第i個序列已經(jīng)被匹配的長度p[i]，以及第i序列的原始長度len[i]。則有兩個剪枝：

剪枝1：直接取最長待匹配長度。1900ms

int h = 0;for(int i = 0; i < n; ++i) {    h = max(len[i] - p[i], h); //最大待匹配長度 }剪枝二：統(tǒng)計(jì)每個序列里面四種序列值，并求得每種序列值的最長長度。將四種序列值加起來就是最長待匹配長度。180ms
int cal() { //至少還需要匹配的長度 	memset(cost, 0, sizeof(cost));	memset(tp, 0, sizeof(tp));	for(int i = 0; i < n; ++i) {		for(int j = p[i]; j < len[i]; ++j) tp[ha[str[i][j]]]++;		for(int j = 0; j < 4; ++j) {			cost[j] = max(cost[j], tp[j]);			tp[j] = 0;		}	}	int h = 0;	for(int i = 0; i < 4; ++i) h += cost[i];	return h; }剪枝二優(yōu)于剪枝一。
AC代碼：180ms
#include<cstdio>#include<cstring>#include<algorithm>#include<map>using namespace std;map<char, int>ha; const int maxn = 10;char str[maxn][maxn];int len[maxn], p[maxn];int n, maxd, pd;int cost[4], tp[4];char ch[] = {'A', 'G', 'C', 'T'};int cal() { //至少還需要匹配的長度 	memset(cost, 0, sizeof(cost));	memset(tp, 0, sizeof(tp));	for(int i = 0; i < n; ++i) {		for(int j = p[i]; j < len[i]; ++j) tp[ha[str[i][j]]]++;		for(int j = 0; j < 4; ++j) {			cost[j] = max(cost[j], tp[j]);			tp[j] = 0;		}	}	int h = 0;	for(int i = 0; i < 4; ++i) h += cost[i];	return h; }int dfs(int cnt) {	int h = cal();	if(h == 0) {		PRintf("%d/n", maxd);		return 1;	}	if(h + cnt > maxd) {		pd = min(h + cnt, pd);		return 0;	}	int old[maxn];	memcpy(old, p, sizeof(old));	for(int i = 0; i < 4; ++i) {		char c = ch[i];		int flag = 0;		for(int j = 0; j < n; ++j) {			if(p[j] < len[j] && str[j][p[j]] == c) {				flag = 1;				++p[j];			}		}		if(flag && dfs(cnt + 1)) return 1;		memcpy(p, old, sizeof(old));	}	return 0; }int main() {	for(int i = 0; i < 4; ++i) ha[ch[i]] = i;	int T;	scanf("%d", &T);	while(T--) {		maxd = 0;		memset(p, 0, sizeof(p));		scanf("%d", &n);		for(int i = 0; i < n; ++i) {			scanf("%s", str[i]);			len[i] = strlen(str[i]);			maxd = max(maxd, len[i]);		}		while(1) {			pd = 1 << 30;			if(dfs(0)) break;			maxd = pd;		}	}	return 0;}如有不當(dāng)之處歡迎指出！