hdu 1560 DNA sequence(迭代加深搜索)

时间:2023-01-21 13:09:09

DNA sequence

Time Limit : 15000/5000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 15   Accepted Submission(s) : 7

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

The twenty-first century is a biology-technology developing century. We know that a gene is made of DNA. The nucleotide bases from which DNA is built are A(adenine), C(cytosine), G(guanine), and T(thymine). Finding the longest common subsequence between DNA/Protein sequences is one of the basic problems in modern computational molecular biology. But this problem is a little different. Given several DNA sequences, you are asked to make a shortest sequence from them so that each of the given sequence is the subsequence of it.

For example, given "ACGT","ATGC","CGTT" and "CAGT", you can make a sequence in the following way. It is the shortest but may be not the only one.

hdu 1560 DNA sequence(迭代加深搜索)

Input

The first line is the test case number t. Then t test cases follow. In each case, the first line is an integer n ( 1<=n<=8 ) represents number of the DNA sequences. The following k lines contain the k sequences, one per line. Assuming that the length of any sequence is between 1 and 5.

Output

For each test case, print a line containing the length of the shortest sequence that can be made from these sequences.

Sample Input

1
4
ACGT
ATGC
CGTT
CAGT

Sample Output

8

Author

LL

Source

HDU 2006-12 Programming Contest
 
 

使用dfs进行搜索,但限制递归深度。

逐步加深搜索深度,直至找到答案。

主函数中, 限制搜索深度,如果无解,就加深1层深度

强力剪枝: 递归函数中, 首先计算最坏情况下,还需要补充长度:

为每个DNA序列还未匹配的长度之和(sum)。

如果现在搜索深度+sum>限定的搜索深度,则返回

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char f[]={'A','T','G','C'};
int flag,i,t,n,maxlen;
int cnt[];
char str[][];
void dfs(int len,int cnt[])
{
if (flag || len>maxlen) return; int sum=;
for(int i=;i<n;i++) //关键 :ida*(迭代加深搜索)
{
int l=strlen(str[i]);
sum=max(sum,l-cnt[i]);
}
if (sum+len>maxlen) return;
if (sum==) {flag=; return;} for(int i=;i<;i++)
{
char x=f[i];
int next[];
int tflag=;
for(int j=;j<n;j++)
if (str[j][cnt[j]]==x)
{
next[j]=cnt[j]+;
tflag=;
} else next[j]=cnt[j];
if (tflag) dfs(len+,next); //更新了才说明有效
}
return;
}
int main()
{
scanf("%d",&t);
for(;t>;t--)
{
scanf("%d",&n);
maxlen=;
for(i=;i<n;i++)
{
scanf("%s",str[i]);
int l=strlen(str[i]);
maxlen=max( maxlen,l );
}
flag=;
memset(cnt,,sizeof(cnt));
for(i=;i<;i++)
{
dfs(,cnt);
if (flag) break;
maxlen++;
}
printf("%d\n",maxlen);
}
return ;
}

hdu 1560 DNA sequence(迭代加深搜索)的更多相关文章

  1. HDU 1560 DNA sequence(DNA序列)

    HDU 1560 DNA sequence(DNA序列) Time Limit: 15000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K  ...

  2. HDU 1560 DNA sequence &lpar;IDA&ast; 迭代加深 搜索&rpar;

    题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1560 BFS题解:http://www.cnblogs.com/crazyapple/p/321810 ...

  3. HDU 1560 DNA sequence (迭代加深搜索)

    The twenty-first century is a biology-technology developing century. We know that a gene is made of ...

  4. hdu 1560 DNA sequence&lpar;搜索&rpar;

    http://acm.hdu.edu.cn/showproblem.php?pid=1560 DNA sequence Time Limit: 15000/5000 MS (Java/Others)  ...

  5. HDU 1560 DNA sequence&lpar;IDA&ast;&rpar;

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1560 题目大意:给出n个字符串,让你找一个字符串使得这n个字符串都是它的子串,求最小长度. 解题思路: ...

  6. HDU 1560 DNA sequence DFS

    题意:找到一个最短的串,使得所有给出的串是它的子序列,输出最短的串的长度,然后发现这个串最长是40 分析:从所给串的最长长度开始枚举,然后对于每个长度,暴力深搜,枚举当前位是哪一个字母,注意剪枝 注: ...

  7. HDU - 1560 DNA sequence

    给你最多8个长度不超过5的DNA系列,求一个包含所有系列的最短系列. 迭代加深的经典题.(虽然自己第一次写) 定一个长度搜下去,搜不出答案就加深大搜的限制,然后中间加一些玄学的减枝 //Twenty ...

  8. HDU 1560 DNA sequence A&ast; 难度&colon;1

    http://acm.hdu.edu.cn/showproblem.php?pid=1560 仔细读题(!),则可发现这道题要求的是一个最短的字符串,该字符串的不连续子序列中包含题目所给的所有字符串 ...

  9. HDU1560&lpar;迭代加深搜索&rpar;

    DNA sequence Time Limit: 15000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Tot ...

随机推荐

  1. GridView的使用

    首先,gridview是封装好的,直接在设计界面使用,基本不需要写代码: 一.绑定数据源 GridView最好与LinQDatasourse配合使用,相匹配绑定数据: 二.样式控制 1.自动套用样式 ...

  2. linq 分类

    linq技术为我们开发人员提供了五个比较实用的数据访问类型: LinQ to Object:可以允许对内存中的类对象查询. LinQ to DataSet:可以对内存中的DataSet缓存数据,执行数 ...

  3. Qtcreator中经常使用快捷键总结

    Qtcreator中经常使用快捷键总结 F1        查看帮助 F2        跳转到函数定义(和Ctrl+鼠标左键一样的效果) Shift+F2    声明和定义之间切换 F4       ...

  4. FusionCharts报错收录

    FusionCharts报错 1.错误一 DesignTimeError:#25081843 flash-chart render Error >>#25081843:IECompatib ...

  5. Android 基础 一 AndroidManifest&period;xml

    一.概述 AndroidManifest.xml是Android应用的入口文件,它描述了package中暴露的组件(activities, services, 等等),他们各自的实现类,各种能被处理的 ...

  6. nginx&colon; &lbrack;emerg&rsqb; getpwnam&lpar;&quot&semi;nginx&quot&semi;&rpar; failed

    搭建LNMP环境的时候,在安装完Nginx后启动测试Nginx服务时发现报如下错误: nginx: [emerg] getpwnam("nginx") failed 这是由于没有创 ...

  7. &period;NET CORE下的Cache

    .NET CORE 下的缓存跟之前ASP.NET下的缓存有所不同,应用.NET CORE缓存首先需要引入Microsoft.Extensions.Caching.Memory程序包 下面简单写了一个C ...

  8. shiro loginUrl拦截无效

    logUrl不拦截 或者 只跳转到/login.jsp 不跳到自己设置登录链接 在springmvc或事务那里 开启spring的显示代理(即cglib),并将shiro的安全管理器交给spring管 ...

  9. vue 新增时清除表单验证注意事项

    // 清除表单校验的提示 if (this.$refs['XXX']) { // 延时执行 this.$nextTick(function () { this.$refs['XXX'].clearVa ...

  10. centos yum安装PHP5&period;5&comma;5&period;6&comma;7&period;0

    默认的版本太低了,手动安装有一些麻烦,想采用Yum安装的可以使用下面的方案:1.检查当前安装的PHP包yum list installed | grep php如果有安装的PHP包,先删除他们 yum ...