题目链接:http://poj.org/problemstatus?problem_id=3691

题目大意

给定一系列代表疾病的DNA序列,同时已知一条DNA序列,计算改变最少的DNA序列来使这个DNA序列不包含疾病的DNA序列

例如:

AAA
AAG
#前面两列代表疾病的DNA序列

AAAG #正常的DNA序列

输出:1     #修改第三个字符即可

解题思路

AC自动机+状态dp
首先由desease的DNA序列,构造出Trie树即AC自动机,也可以叫做DFA图,每个节点代表一种状态,然后利用状态转移的动态规划方法,dp[i][j] 表示到目标串的第 i 个字符,DFA 状态为 j 时的最小修改数量,具体方程分为两种,已知dp[i-1][j]:
1,child[sequence[i]] 状态j的匹配第i个字符的子节点 && !is_danger
dp[i][child[sequence[i]]] = min{dp[i][child[sequence[j]]], dp[i-1][j]}
2,状态j的其他子节点 && is_danger
dp[i][other_child] = min{dp[i][other_child], dp[i-1][other_child] + 1}

最后在所有的dp[len-1][j] &&!is_danger 中找到 最小的值极为所求
更多 >