HDU1560 DNA sequence IDA* + 强力剪枝 [kuangbin带你飞]专题二

        题意：给定一些DNA序列，求一个最短序列能够包含所有序列。

      思路：记录第i个序列已经被匹配的长度p[i]，以及第i序列的原始长度len[i]。则有两个剪枝：

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

int h = 0;for(int i = 0; i < n; ++i) {    h = max(len[i] - p[i], h); //最大待匹配长度 }剪枝二：统计每个序列里面四种序列值，并求得每种序列值的最长长度。将四种序列值加起来就是最长待匹配长度。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; }剪枝二优于剪枝一。
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;}如有不当之处欢迎指出！