题意
给出n( 1 <= n <= 8 )个长度为1~5的DNA序列, 找出一个最短的满足包含所有这些子字符串的字符串，只要字符串中各字母相对位置相同即可。
思路
IDA*
从maxd = lenmax开始加深
AC代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define mst(a) memset(a, 0, sizeof(a));using namespace std;
int maxd, n;
char g[10][6];
int len[10], pos[10];
char DNA[] = "ACGT";
bool flag;void init(){flag = false;mst(g);mst(len);mst(pos);
}void dfs( int d ){int result = 0;for(int i = 0; i < n; i++)result = max(result, len[i]-pos[i]);if( result == 0 ){ flag = true; return; }else if( result > d ) return ; //剪枝int _pos[10]; //用于记录改变前状态for( int i = 0; i < n; i++ )_pos[i] = pos[i];bool ok = false;for( int i = 0; i < 4; i++ ){for( int j = 0; j < n; j++ )if( g[j][pos[j]] == DNA[i] ){pos[j]++;ok = true;}if(ok){dfs(d-1);if( flag ) return;for( int k = 0; k < n; k++ ) //若未成功则还原pos串pos[k] = _pos[k]; }}
}void solve(){for( ; ; maxd++ ){dfs(maxd);if( flag )break;}printf("%d\n",maxd);
}int main()
{int T;scanf("%d",&T);while( T-- ){init();int lenmax = -1;scanf("%d", &n);for( int i = 0; i < n; i++ ){scanf("%s",g[i]);len[i] = strlen(g[i]);pos[i] = 0;lenmax = max(lenmax, len[i]);}maxd = lenmax; //从lenmax开始枚举solve();}return 0;
}
