目录
原题描述：
题目描述
时间：1s 空间：256M
题目描述：
给出 个长度最长为
，仅包含 'A', 'T', 'C', 'G' 这
种字母的DNA子序列字符串，求一个最短的DNA母串，能够包含全部的DNA子序列。
输入格式：
第一行包含一个整数 。
接下来 行，每行一个字符串，仅包含'A', 'T', 'C', 'G' 44 种字母。
输出格式：
输出一个整数表示答案。
样例1输入：
4
ACGT
ATGC
CGTT
CAGT样例1输出：
8约定与提示：
对于100%的数据，
样例解释如图：
主要思路：
考虑暴力，每次枚举四种情况，复杂度：
所以要加一些剪枝。
我们从最开始的时候，求一个最优解，从最优解开始枚举len，接着dfs，如果当前x+当前最优解所需字符长度>枚举的len，就直接结束。
求最优解：
就是把四种字符出现次数取个max，最后相加。
ACcode（有注释）：
#include<bits/stdc++.h>
using namespace std;
int tmp[1010];//待选中的字符序列
int cnt[1010][1010];//记录字符出现了几次
int n;
int a[1010][1010];//记录字符序列（为了好操作）A = 0,T = 1,C = 2,G = 3,a[i][0]是第i个字符串的长度
int b[1010];
int calc()//求最优需要多少个字符（当啥都没选的时候）
{
for(int i=1;i<=n;i++)//枚举每个字符串
{
for(int j=1;j<=a[i][0];j++)
{
cnt[i][a[i][j]]++;//统计出现次数
}
for(int j=0;j<4;j++)
{
b[j] = max(b[j],cnt[i][j]);//算最值
}
}
int ans=0;
for(int i=0;i<4;i++)
{
ans += b[i];//加起来
}
return ans;
}
int calc1(int len)//求1~len匹配后最值
{
memset(b,0,sizeof(b));//清空数组
for(int i=1;i<=n;i++)//枚举每个字符串
{
vector<int> cnt(10);//统计字符
int k=1;
for(int j=1;j<=len;j++)//匹配
{
if(k<=a[i][0]&&tmp[j] == a[i][k])//匹配上了
{
k++;//加1
}
}
for(int j=k;j<=a[i][0];j++)//从没匹配上位置开始
{
cnt[a[i][j]]++;//统计出现次数
}
for(int j=0;j<4;j++)
{
b[j] = max(b[j],cnt[j]);//算最值
}
}
int ans=0;
for(int i=0;i<4;i++)
{
ans += b[i];//加起来
}
return ans;
}
bool dfs(int x,int y,int len)//x是当前位置，y是最优情况下还需要多少字母才成立，len是目标长度
{
// cout<<x<<' '<<y<<'\n';
if(x+y>len+1)//如果最优情况都不满足，就说明不可行
{
return 0;
}
if(x == len+1)//如果成功，返回成功。
{
return 1;
}
for(int i=0;i<4;i++)//枚举当前字符
{
tmp[x] = i;
int tmp1=calc1(x);
if(dfs(x+1,tmp1,len))//如果已经成功，就不用再算了，返回
{
return 1;
}
}
return 0;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
{
string s;
cin>>s;
a[i][0] = s.size();//记录长度
for(int j=0;j<a[i][0];j++)//映射
{
if(s[j] == 'A')
{
a[i][j+1] = 0;
}
else if(s[j] == 'T')
{
a[i][j+1] = 1;
}
else if(s[j] == 'C')
{
a[i][j+1] = 2;
}
else if(s[j] == 'G')
{
a[i][j+1] = 3;
}
}
}
int start = calc();//从最优开始枚举
// cout<<start<<'\n';
for(int i=start;;i++)//枚举
{
if(dfs(1,start,i))//成功，结束
{
cout<<i;
exit(0);
}
}
return 0;
}
