POJ 3691 AC自动机上的dp

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题目大意：

给定一些不合理的DNA序列，再给一段较长的dna序列，问最少修改几次可以使序列中不存在任何不合理序列，不能找到修改方法输出-1

这里你修改某一个点的DNA可能会影响后面，我们不能单纯的找匹配数，因为你找到了你也不一定有方法改变它

这里用DP来解决

判断到第i位dna ，之前dp值保存了前面dna所能到达的所有状态：

dp[i][j] 也就是用了前i个dna所到达的状态至少需要修改的值

从所有状态出发，经过AGCT4种情况到达下一个状态，只要下一个状态不为非法状态即可

过程中只要判断你走的AGCT4种情况是否和当前字符相同，相同说明不用做出改变，即+0 ，否则+1，不断进行更新

 #include <cstdio>

 #include <cstring>

 #include <queue>

 #include <vector>

 #include <iostream>

 #include <algorithm>

 #include <map>

 using namespace std;

 #define clr(x) memset(x , 0 , sizeof(x))

 #define set(x) memset(x , -1 , sizeof(x))

 typedef long long LL ;

 const int CHAR_SIZE = ;

 const int MAX_SIZE = ;

 const int M =  ;

 int n,m,p;

 int mp[];

 struct AC_Machine{

     int ch[MAX_SIZE][CHAR_SIZE] , val[MAX_SIZE] , fail[MAX_SIZE];

     int sz;

     void init(){

         sz = ;

         clr(ch[]) , clr(val);

     }

     void insert(char *s){

         int n = strlen(s);

         int u= ;

         for(int i= ; i<n ; i++){

             int c = mp[s[i]];

             if(!ch[u][c]){

                 clr(ch[sz]);

                 val[sz] = ;

                 ch[u][c] = sz++;

             }

             u = ch[u][c];

         }

         val[u] = ;

     }

     void get_fail(){

         queue<int> Q;

         fail[] = ;

         for(int c= ; c<CHAR_SIZE ; c++){

             int u = ch[][c];

             if(u){Q.push(u);fail[u]=;}

         }

         while(!Q.empty()){

             int r = Q.front();

             Q.pop();

             val[r] |= val[fail[r]];

             for(int c= ; c<CHAR_SIZE ; c++){

                 int u = ch[r][c];

                 if(!u){ch[r][c] = ch[fail[r]][c]; continue;}

                 fail[u] = ch[fail[r]][c];

                 Q.push(u);

             }

         }

     }

 }ac;

 char str[];

 int f[][MAX_SIZE];

 int solve()

 {

     memset(f , 0x3f , sizeof(f));

     f[][] = ;

     int len = strlen(str) , ret=0x3f3f3f3f;

     for(int i= ; i<=len ; i++){

         int v = mp[str[i-]];

         for(int j= ; j<ac.sz ; j++){

             for(int k= ; k<CHAR_SIZE ; k++){

                 if(!ac.val[ac.ch[j][k]]){

                     f[i][ac.ch[j][k]] = min(f[i-][j]+(v==k?:) , f[i][ac.ch[j][k]]);

                 }

             }

         }

     }

     for(int i= ; i<ac.sz ; i++){

         ret = min(ret , f[len][i]);

     }

     if(ret == 0x3f3f3f3f) return -;

     else return ret;

 }

 int main()

 {

    // freopen("in.txt" , "r" , stdin);

    // freopen("out.txt" , "w" , stdout);

     mp['A'] =  , mp['G'] =  , mp['C'] =  , mp['T'] = ;

     int cas = ;

     while(scanf("%d" , &n),n){

         ac.init();

         for(int i= ; i<=n ; i++){

             scanf("%s" , str);

             ac.insert(str);

         }

         ac.get_fail();

         scanf("%s" , str);

         printf("Case %d: " , ++cas);

         printf("%d\n" , solve());

     }

     return ;

 }