hdu 2457 DNA repair-白红宇

hdu 2457 DNA repair

阅读量：6083 次

发布时间：2019-06-20

本文共 2161 字，大约阅读时间需要 7 分钟。

AC自动机+DP。按着自动机跑，（其实是生成新的满足题目要求的串，然后找改变最少的。）但是不能跑到是单词的地方，如果跑到单词的话那么说明改变后的串含有病毒了，不满足题意。然后就是应该怎么跑的问题了，现在我们从自动机的根节点开始跑，如果跑到下一个节点和当前串的字母不一样的话，那么当前位置生成的串是和原串在该位置是有差异的，dp+1，否者的话dp不变。所以dp[ i ][ j ]表示的是匹配到当前匹配串的位置时，跑到自动机的 j 节点需要改变的最少字母数。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #define CLR(a, b) memset(a, b, sizeof(a))using namespace std;const int MAX_NODE = 22 * 55 * 2;const int INF = 0x3f3f3f3f;const int CHILD_NUM = 4;const int N = 1010;class ACAutomaton{private: int chd[MAX_NODE][CHILD_NUM]; int dp[N][MAX_NODE]; int fail[MAX_NODE]; bool val[MAX_NODE]; int Q[MAX_NODE]; int ID[128]; int sz;public: void Initialize() { fail[0] = 0; ID['A'] = 0;ID['G'] = 1; ID['C'] = 2;ID['T'] = 3; } void Reset() { CLR(chd[0] , 0);sz = 1; } void Insert(char *a) { int p = 0; for ( ; *a ; a ++) { int c = ID[*a]; if (!chd[p][c]) { CLR(chd[sz] , 0); val[sz] = false; chd[p][c] = sz ++; } p = chd[p][c]; } val[p] = true; } void Construct() { int *s = Q , *e = Q; for (int i = 0 ; i < CHILD_NUM ; i ++) { if (chd[0][i]) { fail[ chd[0][i] ] = 0; *e ++ = chd[0][i]; } } while (s != e) { int u = *s++; for (int i = 0 ; i < CHILD_NUM ; i ++) { int &v = chd[u][i]; if (v) { *e ++ = v; fail[v] = chd[ fail[u] ][i]; val[v] |= val[fail[v]]; } else { v = chd[ fail[u] ][i]; } } } } int Work(char *ch) { int len, S, T, ret; len = strlen(ch); CLR(dp, INF);dp[0][0] = 0; for(int i = 0; i < len; i ++) for(int j = 0; j < sz; j ++) { if(val[j]) continue; if(dp[i][j] == INF) continue; for(int k = 0; k < 4; k ++) { T = chd[j][k]; if(val[T]) continue; dp[i + 1][T] = min(dp[i + 1][T], dp[i][j] + (ID[ch[i]] != k)); } }ret = INF; for(int i = 0; i < sz; i ++) { ret = min(ret, dp[len][i]); } return ret == INF ? -1 : ret; }} AC;char ch[N];int main(){ //freopen("input.txt", "r", stdin); AC.Initialize(); int n, t, cas = 1; while (scanf("%d", &n), n) { AC.Reset(); for (int i = 0 ; i < n ; i ++) { char temp[55]; scanf("%s", temp); AC.Insert(temp); } scanf("%s", ch); AC.Construct(); printf("Case %d: %d\n", cas ++, AC.Work(ch)); } return 0;}

转载地址：http://dtkwa.baihongyu.com/

你可能感兴趣的文章