修复DNA
2021/8/20 23:08:21
本文主要是介绍修复DNA,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述
给定一些字符串,再给定一个母串,问通过单点修改母串使其不包含任何一个给定字符串的最小操作数是多少?
范围
\(N \leq 50,|S| \leq 1000\)
题解
\(AC自动机,dp\)
设\(f_{i,j}\)表示当前在处理\(DNA\)序列第\(i\)位,\(AC\)自动机上第\(j\)个节点时的答案。
对于\(DNA\)序列的某一位,枚举他的所有方案\(A,G,C,T\),找到\(Trie\)树上与之对应的节点,进行\(dp\)转移:
\(f_{i,p} = max(f_{i,p},f_{i - 1,j} + 1\or0)\)
代码
#include <bits/stdc++.h> using namespace std; const int N = 1010; int t[N][4]; int fl[N]; int cnt[N]; int q[N]; char s[N]; int f[N][N]; int n,idx; int check(char c) { if(c == 'A') return 0; else if(c == 'G') return 1; else if(c == 'C') return 2; else return 3; } void insert(char *s) { int p = 0; for(int i = 0;s[i]; ++i) { int num = check(s[i]); if(!t[p][num]) t[p][num] = ++idx; p = t[p][num]; } cnt[p] = 1; } void build_AC () { queue <int> q; for(int i = 0;i < 4; ++i) { if(t[0][i]) q.push(t[0][i]); } while(!q.empty()) { int u = q.front(); q.pop(); for(int i = 0;i < 4; ++i) { if(!t[u][i]) { t[u][i] = t[fl[u]][i]; } else { fl[t[u][i]] = t[fl[u]][i]; q.push(t[u][i]); cnt[t[u][i]] |= cnt[fl[t[u][i]]]; } } } } int cas; int main () { while(~scanf("%d",&n) and n) { memset(t,0,sizeof t); memset(cnt,0,sizeof cnt); memset(fl,0,sizeof fl); idx = 0; for(int i = 1;i <= n; ++i) { scanf("%s",s); insert(s); } //cout << 1 << endl; build_AC(); //c/out << 1 << endl; scanf("%s",s + 1); int len = strlen(s + 1); memset(f,0x3f,sizeof f); f[0][0] = 0; for(int i = 1;i <= len; ++i) { for(int j = 0;j <= idx; ++j) { for(int k = 0;k < 4; ++k) { int ok = check(s[i]) != k; int p = t[j][k]; if(!cnt[p]) { f[i][p] = min(f[i][p],f[i - 1][j] + ok); } } } } int ans = 0x3f3f3f3f; for(int i = 0;i <= idx; ++i) { ans = min(ans,f[len][i]); } if(ans > 0x3f3f3f3f / 2) ans = -1; printf("Case %d: %d\n",++cas,ans); } return 0; }
这篇关于修复DNA的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-19永别了,微服务架构!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?