大佬教程收集整理的这篇文章主要介绍了DNA sequence HDU - 1560，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
原题链接
考察:IDA*
完全没想到啊....但通过这道题感觉dfs本质就是枚举吧...所以这道题dfs需要一直枚举AGCT,直到所有位置都匹配.
思路:
但是光枚举肯定会TLE的,所以需要剪枝.总共只有8个字符串,每个只有5个字符.最多(不可能达到)要40个字符.所以可以考虑迭代加深.我们在匹配时还可以计算最少还有多少到终态.所以又可以加上预估函数.总的算法就是IDA*.
枚举方法:不停地枚举ATGC直到所有字符串全部被覆盖.对于每一个枚举的字符,用match[i]标识第i个字符串匹配到第match[i]个字符.不停dfs回溯可以枚举所有方法.
A*函数:
策略一:对于每个串取未匹配长度的最大值.即预估函数返回值.858ms
策略二:统计每个串未匹配长度需要的AGCT数量.每个取最大值再累加. 31ms
1 #include <iostream> 2 #include <cString> 3 #include <map> 4 using namespace std; 5 const int N = @H_450_40@6,M = @H_450_40@10,S = @H_450_40@30; 6 map<char,int> mp; 7 int n,len[M],match[M],deep,index[S],cnt[n],tmp[n]; 8 char s[M][n],DNA[@H_450_40@6] = "ATGC"; 9 int h() 10 { 11 // memset(cnt,0,sizeof cnt); 12 memset(tmp,@H_450_40@0,sizeof tmp); 13 for(int i=@H_450_40@1;i<=n;i++) 14 { 15 for(int j=match[i]+@H_450_40@1;j<=len[i];j++) 16 cnt[index[s[i][j]-'A']]++; 17 for(int j=@H_450_40@0;j<@H_450_40@4;j++) 18 tmp[j] = max(tmp[j],cnt[j]),cnt[j] = @H_450_40@0; 19 } 20 int res = @H_450_40@0; 21 for(int i=@H_450_40@0;i<@H_450_40@4;i++) res+=tmp[i]; 22 return res; 23 } 24 bool dfs(int step) 25 { 26 int val = h(); 27 if(!val) return @H_450_40@1; 28 if(step+val>deep) return @H_450_40@0; 29 int b[M]; 30 for(int i=@H_450_40@0;i<@H_450_40@4;i++)//枚举下一个字符 31 { 32 memcpy(b,match,sizeof match); 33 bool ok = @H_450_40@0; 34 for(int j=@H_450_40@1;j<=n;j++)//枚举每一个字符串要匹配的位置是否与该字符匹配 35 if(s[j][match[j]+@H_450_40@1]==DNA[i]) 36 { 37 match[j]++;// 38 ok = @H_450_40@1; 39 } 40 if(ok&&dfs(step+@H_450_40@1)) return @H_450_40@1; 41 memcpy(match,b,sizeof b); 42 } 43 return @H_450_40@0; 44 } 45 int main() 46 { 47 int T; 48 scanf("%d",&T); 49 for(int i=@H_450_40@0;i<@H_450_40@4;i++) index[DNA[i]-'A'] = i; 50 while(T--) 51 { 52 scanf("%d",&n); 53 deep = @H_450_40@0; 54 for(int i=@H_450_40@1;i<=n;i++) 55 { 56 scanf("%s",s[i]+@H_450_40@1); 57 match[i] = @H_450_40@0; 58 len[i] = strlen(s[i]+@H_450_40@1); 59 deep = max(deep,len[i]); 60 } 61 while(!dfs(@H_450_40@0)) deep++; 62 printf("%dn",deep); 63 } 64 return @H_450_40@0; 65 }
以上是大佬教程为你收集整理的DNA sequence HDU - 1560全部内容，希望文章能够帮你解决DNA sequence HDU - 1560所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。