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
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.
Input
Output
Sample Input
1
4
ACGT
ATGC
CGTT
CAGT
Sample Output
8
Author
Source
使用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(迭代加深搜索)的更多相关文章
-
HDU 1560 DNA sequence(DNA序列)
HDU 1560 DNA sequence(DNA序列) Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K ...
-
HDU 1560 DNA sequence (IDA* 迭代加深 搜索)
题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1560 BFS题解:http://www.cnblogs.com/crazyapple/p/321810 ...
-
HDU 1560 DNA sequence (迭代加深搜索)
The twenty-first century is a biology-technology developing century. We know that a gene is made of ...
-
hdu 1560 DNA sequence(搜索)
http://acm.hdu.edu.cn/showproblem.php?pid=1560 DNA sequence Time Limit: 15000/5000 MS (Java/Others) ...
-
HDU 1560 DNA sequence(IDA*)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1560 题目大意:给出n个字符串,让你找一个字符串使得这n个字符串都是它的子串,求最小长度. 解题思路: ...
-
HDU 1560 DNA sequence DFS
题意:找到一个最短的串,使得所有给出的串是它的子序列,输出最短的串的长度,然后发现这个串最长是40 分析:从所给串的最长长度开始枚举,然后对于每个长度,暴力深搜,枚举当前位是哪一个字母,注意剪枝 注: ...
-
HDU - 1560 DNA sequence
给你最多8个长度不超过5的DNA系列,求一个包含所有系列的最短系列. 迭代加深的经典题.(虽然自己第一次写) 定一个长度搜下去,搜不出答案就加深大搜的限制,然后中间加一些玄学的减枝 //Twenty ...
-
HDU 1560 DNA sequence A* 难度:1
http://acm.hdu.edu.cn/showproblem.php?pid=1560 仔细读题(!),则可发现这道题要求的是一个最短的字符串,该字符串的不连续子序列中包含题目所给的所有字符串 ...
-
HDU1560(迭代加深搜索)
DNA sequence Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Tot ...
随机推荐
-
GridView的使用
首先,gridview是封装好的,直接在设计界面使用,基本不需要写代码: 一.绑定数据源 GridView最好与LinQDatasourse配合使用,相匹配绑定数据: 二.样式控制 1.自动套用样式 ...
-
linq 分类
linq技术为我们开发人员提供了五个比较实用的数据访问类型: LinQ to Object:可以允许对内存中的类对象查询. LinQ to DataSet:可以对内存中的DataSet缓存数据,执行数 ...
-
Qtcreator中经常使用快捷键总结
Qtcreator中经常使用快捷键总结 F1 查看帮助 F2 跳转到函数定义(和Ctrl+鼠标左键一样的效果) Shift+F2 声明和定义之间切换 F4 ...
-
FusionCharts报错收录
FusionCharts报错 1.错误一 DesignTimeError:#25081843 flash-chart render Error >>#25081843:IECompatib ...
-
Android 基础 一 AndroidManifest.xml
一.概述 AndroidManifest.xml是Android应用的入口文件,它描述了package中暴露的组件(activities, services, 等等),他们各自的实现类,各种能被处理的 ...
-
nginx: [emerg] getpwnam(";nginx";) failed
搭建LNMP环境的时候,在安装完Nginx后启动测试Nginx服务时发现报如下错误: nginx: [emerg] getpwnam("nginx") failed 这是由于没有创 ...
-
.NET CORE下的Cache
.NET CORE 下的缓存跟之前ASP.NET下的缓存有所不同,应用.NET CORE缓存首先需要引入Microsoft.Extensions.Caching.Memory程序包 下面简单写了一个C ...
-
shiro loginUrl拦截无效
logUrl不拦截 或者 只跳转到/login.jsp 不跳到自己设置登录链接 在springmvc或事务那里 开启spring的显示代理(即cglib),并将shiro的安全管理器交给spring管 ...
-
vue 新增时清除表单验证注意事项
// 清除表单校验的提示 if (this.$refs['XXX']) { // 延时执行 this.$nextTick(function () { this.$refs['XXX'].clearVa ...
-
centos yum安装PHP5.5,5.6,7.0
默认的版本太低了,手动安装有一些麻烦,想采用Yum安装的可以使用下面的方案:1.检查当前安装的PHP包yum list installed | grep php如果有安装的PHP包,先删除他们 yum ...