HDU - 1560 DNA sequence

题意：看图就明白了

思路：迭代深搜，用到了剪枝，如果当前至少需要的加上深度就可以剪掉

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 10;

int len[MAXN],n,now[MAXN];
char str[MAXN][MAXN],ans[100];
char name[] = "ACGT";
int cnt[MAXN][MAXN],deep;

int trans(char ch){
	for (int i = 0; i < 4; i++)
		if (ch == name[i])
			return i;
}

int fuc(){
	int num[4],fac[4];
	for (int j = 0; j < 4; j++)
		fac[j] = 0;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < 4; j++)
			num[j] = 0;
		for (int j = now[i]; j < len[i]; j++)
			num[cnt[i][j]]++;
		for (int j = 0; j < 4; j++)
			if (num[j] > fac[j])
				fac[j] = num[j];
	}
	for (int j = 1; j < 4; j++)
		fac[0] += fac[j];
	return fac[0];
}

int dfs(int dep){
	int vis[10];
	if (dep+fuc() > deep)
		return 0;
	if (dep == deep)
		return 1;
	for (int i = 0; i < 4; i++){
		ans[dep] = name[i];
		for (int j = 0; j < n; j++)
			if (ans[dep] == str[j][now[j]]){
				vis[j] = 1;
				now[j]++;
			}
			else vis[j] = 0;
		for (int j = 0; j < n; j++)
			if (vis[j]){
				if (dfs(dep+1))
					return 1;
				break;
			}
		for (int j = 0; j < n; j++)
			if (vis[j])
				now[j]--;
	}
	return 0;
}

int main(){
	int t;
	scanf("%d",&t);
	while (t--){
		scanf("%d",&n);
		for (int i = 0; i < n; i++){
			scanf("%s",str[i]);
			len[i] = strlen(str[i]);
			for (int j = 0; j < len[i]; j++)
				cnt[i][j] = trans(str[i][j]);
		}
		deep = 1;
		while (1){
			for (int i = 0; i < n; i++)
				now[i] = 0;
			if (dfs(0))
				break;
			deep++;
		}
		printf("%d\n",deep);
	}
	return 0;
}

HDU - 1560 DNA sequence,布布扣,bubuko.com

HDU - 1560 DNA sequence

原文：http://blog.csdn.net/u011345136/article/details/21993879