给你若干小段DNA序列(字符串),请你找到一个DNA序列(字符串),使得这些小段DNA序列(字符串)都能被这个字符串的子序列(非字串,子序列可不连续)匹配。
输出最小长度。
IDA*
容易分析出,数据庞大,而正解大概率在比较小的层数,便选取IDA*
剪枝
拿到题目,犹豫怎么搜,果然还是不够暴力。。
手动加O2是因为昨日CF,本地与OJ输出不同的惨痛教训。OnO
#pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long LL;
int n, depth;
int len[12], idx[12];
char DNA[5] = "ACGT";
char s[12][50];
bool dfs(int u)
{
if (u == depth)
{
for (int i = 1; i <= n; i++)
if (len[i] != idx[i])
return false;
// cout << s[0] << endl;
return true;
}
for (int i = 1; i <= n; i++)
if (len[i] - idx[i] > depth - u)
return false;
// cout << s[0] << endl;
// for (int i = 1; i <= n; i++)
// cout << idx[i] << ' ' << len[i] << endl;
// cout << endl;
for (int i = 0; i < 4; i++)
{
int rec[12], rec_idx = 0; // 为局部变量,变成全局,导致数据混乱
s[0][len[0]++] = DNA[i];
for (int j = 1; j <= n; j++)
{
if (idx[j] < len[j] && s[j][idx[j]] == s[0][len[0] - 1])
{
rec[rec_idx++] = j;
idx[j]++;
}
}
if (dfs(u + 1))
return true;
for (int j = 0; j < rec_idx; j++)
idx[rec[j]]--;
len[0]--;
}
return false;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
// freopen("i.txt", "r", stdin);
// freopen("o.txt", "w", stdout);
int T;
cin >> T;
while (T--)
{
depth = 1;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> s[i];
len[i] = strlen(s[i]);
depth = max(depth, len[i]);
}
// 回来一遍缺少初始化,且在里面不需要,因为dfs会还原
memset(idx, 0, sizeof idx);
s[0][0] = '\0';
len[0] = 0;
while (!dfs(0))
depth++;
cout << depth << endl;
}
return 0;
}