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
题意就是给出N个DNA序列，要求出一个包含这n个序列的最短序列是多长
#include#include #include #include using namespace std; int n,deep; char c[10] = "ACGT"; struct node { char s[10]; int len; } a[10]; int pos[10];//记录第i个序列正在使用第几个位置 int get_h() { int ans = 0; for(int i = 1; i<=n; i++) ans = max(ans,a[i].len-pos[i]);//找出在当前情况下最长的未被匹配的长度围殴估测长度 return ans; } int dfs(int step) { if(step+get_h()>deep)//当前长度+估测的长度比deep还大的话，也就没有继续往下搜索的必要了 return 0; if(!get_h()) return 1; int i,j; int tem[10]; for(i = 0; i<4; i++) { int flag = 0; for(j = 1; j<=n; j++) tem[j] = pos[j];//先将pos保存起来 for(j = 1; j<=n; j++) { if(a[j].s[pos[j]] == c[i])//当前这位符合，则该串的位置往后移一位 { flag = 1; pos[j]++; } } if(flag)//有符合的，则往下搜索 { if(dfs(step+1)) return 1; for(j = 1; j<=n; j++)//还原 pos[j] = tem[j]; } } return 0; } int main() { int t,i,j,maxn; cin >> t; while(t--) { cin>>n; maxn = 0; for(i = 1; i<=n; i++) { cin>>a[i].s; a[i].len = strlen(a[i].s); maxn = max(maxn,a[i].len); pos[i] = 0; } deep = maxn; while(1) { if(dfs(0))break; deep++; } cout << deep << endl; } return 0; }