$$\color{Purple}{kuangbin题解目录}$$
描述
DNA 序列可以视为由大写字母 $A$,$C$,$G$,$T$ 构成的字符串。
给定 $n$ 个 DNA 序列,请你构造一个序列,要求:
- 每个给定序列都是构造序列的子序列。
- 构造序列的长度尽可能短。
例如,给定序列 ACGT
、ATGC
、CGTT
和 CAGT
,你可以按以下方式构造序列。
请你输出构造序列的最小可能长度。
输入格式
第一行包含整数 $T$,表示共有 $T$ 组测试数据。
每组数据第一行包含整数 $n$。
接下来 $n$ 行,每行包含一个给定序列。
输出格式
每组数据输出一行答案,一个整数表示构造序列的最小可能长度。
数据范围
$1 \\le T \\le 100$,
$1 \\le n \\le 8$,
给定序列长度 $\[1,5\]$。
输入样例:
1
4
ACGT
ATGC
CGTT
CAGT
输出样例:
8
思路
- 用
IDA*
解决该题,由于序列中只存在$4$种元素(ACGT
),故可从当前所有字符串的最大长度开始枚举(不用从深度为$0$开始枚举,加快效率).- 此题的估价函数为每个字符串剩余没加入的字符的长度的
最大值
.- 注意需要保存当前字符串正在使用的字符位置,以及原来的情况(即该数组需放在
迭代加深
的函数中,不应放在全局)方便恢复现场.
代码
// Problem: DNA序列
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4234/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-01-12 17:31:01
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#define MAXN 110
using namespace std;
typedef long long ll;
int t,n;
string s[MAXN];
int len[MAXN];//存储每个字符串的长度
int pos[MAXN];//当前字符串正在使用的字符位置
string op="ACGT";
int f()//估价函数
{
int res=0;
for(int i=0;i<=n-1;i++)
res=max(res,len[i]-pos[i]);
//预计长度-->max{剩下没用的长度=该字符串的长度-当前字符串正在使用的字符位置}
return res;
}
int dfs(int root,int depth)
{
if(f()+root>depth)//当前长度 + 预计长度>当前迭代最大深度
return 0;
if(f()==0)//预计长度为0,表示已完成所有字符串
return 1;
int temp[MAXN];//暂存原来的pos位置
for(int i=0;i<=3;i++)
{
int flag=0;
for(int j=0;j<=n-1;j++)//遍历所有字符串
{
temp[j]=pos[j];
if(s[j][pos[j]]==op[i])
{
pos[j]++;
flag=1;
}
}
if(flag==1)
{
if(dfs(root+1,depth)==1)
return 1;
for(int j=0;j<=n-1;j++)//恢复现场
pos[j]=temp[j];
}
}
return 0;
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
cin >> t;
while(t--)
{
memset(pos,0,sizeof(pos));
int depth=0;
cin >> n;
for(int i=0;i<=n-1;i++)
{
cin >> s[i];
len[i]=s[i].size();
depth=max(depth,len[i]);
}
while(dfs(0,depth)==0)
depth++;
cout << depth << endl;
}
return 0;
}