問(wèn)題描述：
構(gòu)造一個(gè)串，使得它包含所有的給定DNA序列，并且要求長(zhǎng)度最短。
采用dfs策略，對(duì)于每個(gè)串定義1個(gè)指針，當(dāng)全部指針為串尾時(shí)判斷構(gòu)造的長(zhǎng)度，由于狀態(tài)空間過(guò)大，但是又存在冗余搜索，可以用迭代加深將狀態(tài)減少。最長(zhǎng)待構(gòu)造長(zhǎng)度 + 當(dāng)前長(zhǎng)度 < 迭代的最大深度則直接return，大大減少了狀態(tài)數(shù)。
代碼如下：
#include <iostream>
using namespace std;
struct point 
{
int poi[8];
}temp;
char map[9][7];
int len[9];
int Min;
char DNA[] = {'A', 'C', 'G', 'T'};
int n;
int dfs(point tp, int sum, int depth) {
int i, j;
point temp;
if(sum > depth)
return 0;
for(i = 0; i < n; i++) {
if( len[i] - tp.poi[i] + sum > depth)
return 0;
}
for(i = 0; i < n; i++) {
if(map[i][ tp.poi[i] ])
break;
}
if(i == n) {
return 1;
}
int flag;
for(i = 0; i < 4; i++) {
flag = 0;
for(j = 0; j < n; j++) {
if(map[j][ tp.poi[j] ] == DNA[i]) {
flag = 1;
temp.poi[j] = tp.poi[j] + 1;
}else
temp.poi[j] = tp.poi[j];
}
if(flag)
if ( dfs(temp, sum + 1, depth) )
return 1;
}
return 0;
}
int main() {
int t, i;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
for(i = 0; i < n; i++) {
scanf("%s", map[i]);
len[i] = strlen(map[i]);
}
for(i = 0; i < n; i++) {
temp.poi[i] = 0;
}
for(i = 1; ; i++) {
if( dfs(temp, 0, i) )
break;
}
printf("%d\n", i);
}
return 0;
}