题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1560
题目大意：给出n个字符串，让你找一个字符串使得这n个字符串都是它的子串，求最小长度。
解题思路：迭代加深搜索，迭代加深搜索，就是限制DFS的深度deep，若搜不到答案，则加深深度，重新搜索，这样就防止了随着深度不断加深而进行的盲目搜索。这题的迭代深度deep以这n个子串中的最长长度作为起点，不断+1，知道找到符合条件的字符串。每次DFS的时候，都要判断一下，当前的深度＋最少还有加深的深度是否大于限制的长度，若是，则返回上一层。
代码：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<string>
using namespace std;
typedef long long LL;
const int inf=0x3f3f3f3f; int n,deep,ans;
char DNA[]="ACGT";
char str[][]; int Max(int a,int b){
return a>b?a:b;
} void dfs(int index,int len[]){
if(ans!=-)
return;
int h=;//接下来至少还要增加的字符长度
for(int i=;i<=n;i++)
h=Max(h,strlen(str[i])-len[i]);
if(h==){
ans=index;
return;
}
if(h+index>deep)//当前深度+预测最小深度>限制深度
return;
int pos[]={};
for(int i=;i<;i++){
bool flag=false;
for(int j=;j<=n;j++){
if(str[j][len[j]]==DNA[i]){
flag=true;
pos[j]=len[j]+;
}
else
pos[j]=len[j];
}
if(flag&&index+<=deep)//剪枝，！flag说明无论加什么都无法使n个字符串都为子串
dfs(index+,pos);
}
} int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
int mlen=;//最大子串长度
for(int i=;i<=n;i++){
scanf("%s",str[i]);
mlen=Max(strlen(str[i]),mlen);
} int pos[]={};//n个字符串当前匹配到的位置
deep=mlen;
ans=-;
while(){
dfs(,pos);
if(ans!=-)
break;
deep++;
}
printf("%d\n",ans);
}
return ;
}