題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1560

題意：從ｎ個串中找出一個最短的公共串,，該公共串對于n個字符串不要求連續，即只要保持相對順序就好。

解題思路：

根據數據量這題可以用搜索，通過這題學到了迭代加深搜索。

我們可以去搜索最后滿足條件的串，但這題的關鍵是如何去找匹配，我們可以定義一個數組len[i],表示搜到當前這個串時，第i個串可以匹配到的位置。這里想通了，剩下的就是簡單的搜索了。

#include<iostream> #include<cstdio> #include<cstring> using namespace std;int n,ans,deep,size[10]; char str[10][10]; //記錄n個字符串 char DNA[4]={'A','C','G','T'}; //一共四種可能 void dfs(int cnt,int len[]) {if(cnt > deep) return; //大于限制的深度，不用往下搜索 int tmp = 0; 預計還要匹配的字符串的最大長度 for(int i = 0; i < n; i++){if(size[i] - len[i] > tmp)tmp = size[i] - len[i];}if(tmp == 0) //條件全部滿足即為最優解 {ans = cnt;return;}if(cnt + tmp > deep) return;for(int i = 0; i < 4; i++){int pos[10],flag = 0;for(int j = 0; j < n; j++){if(str[j][len[j]] == DNA[i]){flag = 1;pos[j] = len[j] + 1;}else pos[j] = len[j];}if(flag) dfs(cnt+1,pos);if(ans != -1) break;} }int main() {int t;scanf("%d",&t);while(t--){scanf("%d",&n);deep = 0;for(int i = 0; i < n; i++){scanf("%s",str[i]);size[i] = strlen(str[i]);if(size[i] > deep)deep = size[i];}ans = -1;int pos[10] = {0};//記錄n個字符串目前匹配到的位置 while(true){dfs(0,pos);if(ans != -1) break;deep++;}printf("%d\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的hdu 1560 DNA sequence(迭代加深搜索)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。