首页 > 代码库 > [poj 3691]DNA repair

[poj 3691]DNA repair

2024-07-17 00:14:33   221人阅读

好久没刷 poj 了，今天练习 AC 自动机时去水了一发喵~

在 poj 上 A 题的感觉并没有 BZOJ 上那么愉悦，准确的说是痛不欲生

真是应了那句老话，你再慢也有比你慢的，你再快也有比你快的……

跪求那些 0ms 的代码啊，还有那么多人都只跑了 32ms 啊！！

果然还是我太弱了吗？一定是我还太弱了 TAT 

 

一道裸裸的 AC 自动机上 dp 

令 dp[i][j] 表示母串的前 i 个字母遍历 AC 自动机，使之到达 j 节点，至少要修改多少个字母

dp[i+1][k]=min(dp[i+1][k], dp[i][j]+CHAR(j->k)!=s[i])  { k 不为匹配点}

CHAR(j->k) 是指在 AC 自动机上从点 j 转移到点 k 的边时经过的字母

答案就是 min{dp[len(s)][i]} 了喵~

 

我才不会说我是来晒我的 AC 自动机代码的呢~  (虽然被 poj 的各大神犇搞得一点优越感都没有……)

 

  1 #include <cstdio>  2 #include <cstring>  3 const int inf=0x3F3F3F3F;  4 const int sizeOfText=1024;  5 const int sizeOfType=4;  6 const int sizeOfMemory=1024;  7   8 namespace trieDfa  9 { 10     struct node 11     { 12         int idx; 13         bool end; 14         node * fail; 15         node * ch[sizeOfType]; 16     }; 17     node * dfa; 18     node memory[sizeOfMemory]; int port; 19     node * E[sizeOfMemory]; 20     inline node * newnode() 21     { 22         node * ret=memory+port; 23         E[ret->idx=port++]=ret; 24         ret->end=0; 25         ret->fail=NULL; 26         memset(ret->ch, 0, sizeof(ret->ch)); 27         return ret; 28     } 29     inline void clear() {port=0; dfa=newnode();} 30  31     inline int ord(char ch) 32     { 33         switch (ch) 34         { 35             case ‘A‘:return 0; 36             case ‘G‘:return 1; 37             case ‘C‘:return 2; 38             case ‘T‘:return 3; 39         } 40     } 41     inline void insert(char * s) 42     { 43         int len=strlen(s); 44         node * t=dfa; 45         for (int i=0;i<len;i++) 46         { 47             if (!t->ch[ord(s[i])]) t->ch[ord(s[i])]=newnode(); 48             t=t->ch[ord(s[i])]; 49         } 50         t->end=1; 51     } 52     inline void buildDfa() 53     { 54         static node * queue[sizeOfMemory]; 55         int l=0, r=0; 56  57         dfa->fail=dfa; 58         for (int i=0;i<sizeOfType;i++) 59             if (!dfa->ch[i]) dfa->ch[i]=dfa; 60             else dfa->ch[i]->fail=dfa, queue[r++]=dfa->ch[i]; 61  62         for ( ;l<r; ) 63         { 64             node * u=queue[l++]; 65             u->end|=u->fail->end; 66             for (int i=0;i<sizeOfType;i++) 67                 if (u->ch[i]) 68                 { 69                     u->ch[i]->fail=u->fail->ch[i]; 70                     queue[r++]=u->ch[i]; 71                 } 72                 else 73                     u->ch[i]=u->fail->ch[i]; 74         } 75     } 76 } 77 using namespace trieDfa; 78  79 int cases, n; 80 char str[sizeOfText]; 81 int f[sizeOfText][sizeOfMemory]; 82 inline int min(int x, int y) {return x<y?x:y;} 83 inline int dp(char * ); 84  85 int main() 86 { 87     for (scanf("%d", &n);n;scanf("%d", &n)) 88     { 89         clear(); 90         for (int i=1;i<=n;i++) 91         { 92             scanf("%s", str); 93             insert(str); 94         } 95         buildDfa(); 96         scanf("%s", str); 97         printf("Case %d: %d\n", ++cases, dp(str)); 98     } 99 100     return 0;101 }102 inline int dp(char * s)103 {104     int len=strlen(s);105     int ret=inf;106 107     memset(f, inf, sizeof(f));108     f[0][0]=0;    109     for (int i=0;i<len;i++)110         for (int j=0;j<port;j++)111             for (int k=0;k<sizeOfType;k++)112                 if (!E[j]->ch[k]->end)113                     f[i+1][E[j]->ch[k]->idx]=min(f[i+1][E[j]->ch[k]->idx], f[i][j]+(ord(s[i])!=k));114     for (int i=0;i<port;i++) ret=min(ret, f[len][i]);    115 116     return ret==inf?-1:ret;117 }
本傻装B系列

 


联系
我们