G - DNA sequence HDU - 1560

2-Day-G
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.

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
题意:高中生物DNA序列好怀念,给出N个DNA序列,要求出一个包含这n个序列的最短序列是多长。

代码如下:
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define clr(a,b) memset(a,b,sizeof(a));
using namespace std;</cstdio></algorithm></cstring></iostream>

bool flag=0;
char map[10][10],str[]="ACGT";
int point[10];
int num[10];
int n;

int estimation()
{
int ans=0;
for(int i=0;i<n;i++)
{
ans=max(ans,num[i]-point[i]);
}
return ans;
}

void dfs(int maxstep)
{
if(estimation()==0)
{
flag=true;
return;
}
if(maxstep<estimation())
{
return;
}
int repetition[10];
for(int i=0;i<n;i++)
repetition[i]=point[i];
int yes=0;
for(int i=0;i<4;i++)
{
for(int j=0;j<n;j++)
{
if(map[j][point[j]]==str[i])
{
yes=1;
point[j]++;
}
}
if(yes)
{
dfs(maxstep-1);
if(flag)
return;
for(int k=0;k<n;k++)
point[k]=repetition[k];
}

}

}

int main()
{
int t;
cin>>t;
while(t--)
{
cin>>n;
clr(point,0)
clr(num,0)
clr(map,'\0')
flag=0;
for(int i=0;i<n;i++)
{
scanf("%s",map[i]);
num[i]=strlen(map[i]);
}
int result=0;
for(int i=0;i<n;i++)
result=max(result,num[i]);
while(1)
{
dfs(result);
if(flag==true)
{
cout<<result<<endl;
break;
}
result++;
}
}
return 0;
}

全部评论

相关推荐

当初高考报计算机真是造大孽了啊!卷的飞起!哪都是计算机的人,考研,考公,找工作全他奶的计算机的人,太难了。国企也是。关键一届比一届卷,造大孽了!
_Lyrics_:因为计算机,没有体验到快乐的大学研究生时光,好不容易修完课程就要出去实习,看着别人专业可以一起搓麻将,游山玩水,而我却要自己一个人住在北上不到十平米的出租屋,每天两点一线
点赞 评论 收藏
分享
叶扰云倾:进度更新,现在阿里云面完3面了,感觉3面答得还行,基本都答上了,自己熟悉的地方也说的比较细致,但感觉面试官有点心不在焉不知道是不是不想要我了,求阿里收留,我直接秒到岗当阿里孝子,学校那边的房子都退租了,下学期都不回学校,全职猛猛实习半年。这种条件还不诱人吗难道 然后现在约到了字节的一面和淘天的复活赛,外加猿辅导。华为笔试完没动静。 美团那边之前投了个base广州的,把我流程卡麻了,应该是不怎么招人,我直接简历挂了,现在进了一个正常的后端流程,还在筛选,不知道还有没有hc。
点赞 评论 收藏
分享
04-17 10:16
门头沟学院 Java
小浪_coder:24届很难找了,马上25的都毕业了还有很多没找到的
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务