HDU 1560

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=1560

题意描述

现在有n个DNA串,串长不超过5,n<=8。求包含这些子串的最短字符串长度。

思路分析

使用迭代加深搜索来计算最短的字符串,当最长剩余字符串长度+当前深度>限定深度的时候,需要剪枝。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

int n;
const int maxn = 10;
const char DNA[] = {"ACGT"};
char str[maxn][maxn];
int len[maxn];
int res[maxn];

bool IDA_star(int* cur, int x, int dep){
int tmp[maxn];
// 如果当前的层数+剩余最长字符串长度大于目标深度的话,剪枝
for (int i = 0; i < n; ++i){
if (len[i] - cur[i] + x > dep){
return false;
}
}
// 如果当前所有的字符串都已经处理完毕,返回
bool finish_all = true;
for (int i = 0; i < n; ++i){
if (str[i][cur[i]]){
finish_all = false;
}
}
if (finish_all){
return true;
}
// 判断是否存在于某一个字符串的处理位置,存在的话就搜索,不存在则剪枝
bool exist_in_str;
for (int i = 0; i < 4; ++i){
exist_in_str = false;
for (int j = 0; j < n; ++j){
if (DNA[i] == str[j][tmp[j] = cur[j]]){
++tmp[j];
exist_in_str = true;
}
}
if (exist_in_str and IDA_star(tmp, x+1, dep)){
return true;
}

}
return false;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin >> T;
while (T--){
cin >> n;
for (int i = 0; i < n; ++i){
cin >> str[i];
len[i] = strlen(str[i]);
}
memset(res, 0, sizeof res);
int ans = 0;
// 迭代加深
while (!IDA_star(res, 0, ans)) ++ans;
cout << ans << endl;
}
return 0;
}