问题描述:
构造一个串,使得它包含所有的给定DNA序列,并且要求长度最短。
采用dfs策略,对于每个串定义1个指针,当全部指针为串尾时判断构造的长度,由于状态空间过大,但是又存在冗余搜索,可以用迭代加深将状态减少。最长待构造长度 + 当前长度 < 迭代的最大深度则直接return,大大减少了状态数。
代码如下:
#include <iostream>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
struct point
{
int poi[8];
}temp;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
char map[9][7];
int len[9];
int Min;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
char DNA[] =
{'A', 'C', 'G', 'T'};
int n;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int dfs(point tp, int sum, int depth)
{
int i, j;
point temp;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if(sum > depth)
return 0;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 0; i < n; i++)
{
if( len[i] - tp.poi[i] + sum > depth)
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 0; i < n; i++)
{
if(map[i][ tp.poi[i] ])
break;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(i == n)
{
return 1;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int flag;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 0; i < 4; i++)
{
flag = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(j = 0; j < n; j++)
{
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
int t, i;
scanf("%d", &t);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(t--)
{
scanf("%d", &n);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 0; i < n; i++)
{
scanf("%s", map[i]);
len[i] = strlen(map[i]);
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 0; i < n; i++)
{
temp.poi[i] = 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i = 1; ; i++)
{
if( dfs(temp, 0, i) )
break;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
printf("%d\n", i);
}
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)