题意：

已知一个DNA串和一些病毒DNA序列，求出最少改变DNA串中多少个字符，能使得串中不包含任意一个病毒序列。

 

题解：

嗯，和上一个trie图一样，把病毒建成trie，只要母串不能再trie上走到危险节点即可（危险节点就是病毒dna序列的终止的那个被标有fg的节点）。

然后trie图上的dp，要走到危险节点的时候，枚举转移即可。

 

 

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6  7 #define M 1111 8 #define N 111 9 #define INF 0x3f3f3f3f10 11 using namespace std;12 13 struct TR14 {15     int son[4]; int f; bool fg;16 }tr[N*N];17 18 int map[N],cnt,q[N*N],n,m,cas;19 char str[N],a[M];20 int dp[M][N*N];21 22 inline void insert(char *s)23 {24     int len=strlen(s+1);25     int now=1;26     for(int i=1;i<=len;i++)27     {28         if(!tr[now].son[map[s[i]]]) tr[now].son[map[s[i]]]=++cnt;29         now=tr[now].son[map[s[i]]];30     }31     tr[now].fg=true;32 }33 34 inline void build()35 {36     int h=1,t=2,sta,now,tmp;37     q[1]=1;38     while(h