題目，求最短的包含所有n個DNA片段且不包含任何一個病毒片段的序列。

容易用所有DNA片段和病毒片段建一個AC自動機，構造fail時處理一下各個結點后綴是DNA或者病毒的情況，然后dp[S][u]表示包含DNA片段的集合是S的且后綴狀態是自動機第u個結點的最短序列長度，然后順著AC自動機避開病毒串轉移。

不過構建的AC自動機結點上限60000左右，集合有1024個狀態，這樣內存開不下。看了題解，原來不必要考慮自動機所有結點——

• dp[S][u]表示包含DNA片段集合是S且后綴是第u個DNA片段的最短序列長度
• 通過BFS預處理出各個DNA片段到其他DNA片段在AC自動機上的距離，要注意某些DNA片段的后綴包含其他DNA片段的情況，還有跳過后綴包含病毒串的結點。
• 轉移就是dp[S][u]=max(dp[S-{u}][v]+dist[v][u])（v∈S-{u}）

這個解法的正確性我還得消化消化。。

1 #include<cstdio> 2 #include<cstring> 3 #include<queue> 4 #include<algorithm> 5 using namespace std; 6 #define INF (1<<29) 7 #define MAXN 66666 8 int tn,ch[MAXN][2],fail[MAXN],flag[MAXN]; 9 int idx[11]; 10 void insert(char *s,int k){ 11 int x=0; 12 for(int i=0; s[i]; ++i){ 13 int y=s[i]-'0'; 14 if(ch[x][y]==0) ch[x][y]=++tn; 15 x=ch[x][y]; 16 } 17 if(k==-1 || flag[x]==-1) flag[x]=-1; 18 else{ 19 idx[k]=x; 20 flag[x]|=(1<<k); 21 } 22 } 23 int que[MAXN],front,rear; 24 void getfail(){ 25 memset(fail,0,sizeof(fail)); 26 front=rear=0; 27 if(ch[0][0]) que[rear++]=ch[0][0]; 28 if(ch[0][1]) que[rear++]=ch[0][1]; 29 while(front<rear){ 30 int x=que[front++]; 31 for(int i=0; i<2; ++i){ 32 if(ch[x][i]){ 33 que[rear++]=ch[x][i]; 34 fail[ch[x][i]]=ch[fail[x]][i]; 35 if(flag[ch[x][i]]==-1 || flag[ch[fail[x]][i]]==-1) flag[ch[x][i]]=-1; 36 else flag[ch[x][i]]|=flag[ch[fail[x]][i]]; 37 }else ch[x][i]=ch[fail[x]][i]; 38 } 39 } 40 } 41 42 int n,m,dist[MAXN],G[11][11]; 43 void BFS(int k){ 44 memset(dist,0,sizeof(dist)); 45 dist[idx[k]]=1; 46 front=rear=0; 47 que[rear++]=idx[k]; 48 while(front<rear){ 49 int x=que[front++]; 50 if(flag[x]){ 51 for(int i=0; i<n; ++i){ 52 if(((flag[x]>>i)&1)==0) continue; 53 G[k][i]=min(G[k][i],dist[x]-1); 54 } 55 } 56 for(int i=0; i<2; ++i){ 57 int y=ch[x][i]; 58 if(flag[y]==-1 || dist[y]) continue; 59 dist[y]=dist[x]+1; 60 que[rear++]=y; 61 } 62 } 63 } 64 int d[1<<10][11],len[11]; 65 int main(){ 66 char str[1111]; 67 while(~scanf("%d%d",&n,&m) && (n||m)){ 68 tn=0; 69 memset(ch,0,sizeof(ch)); 70 memset(flag,0,sizeof(flag)); 71 for(int i=0; i<n; ++i){ 72 scanf("%s",str); 73 insert(str,i); 74 len[i]=strlen(str); 75 } 76 for(int i=0; i<m; ++i){ 77 scanf("%s",str); 78 insert(str,-1); 79 } 80 getfail(); 81 for(int i=0; i<n; ++i){ 82 for(int j=0; j<n; ++j) G[i][j]=INF; 83 } 84 for(int i=0; i<n; ++i){ 85 BFS(i); 86 } 87 for(int i=0; i<(1<<n); ++i){ 88 for(int j=0; j<n; ++j) d[i][j]=INF; 89 } 90 for(int i=0; i<n; ++i){ 91 d[1<<i][i]=len[i]; 92 } 93 for(int i=1; i<(1<<n); ++i){ 94 for(int j=0; j<n; ++j){ 95 if(((i>>j)&1)==0) continue; 96 for(int k=0; k<n; ++k){ 97 if(((i>>k)&1)==0 || j==k) continue; 98 d[i][j]=min(d[i][j],d[i^(1<<j)][k]+G[k][j]); 99 } 100 } 101 } 102 int res=INF; 103 for(int i=0; i<n; ++i) res=min(res,d[(1<<n)-1][i]); 104 printf("%d\n",res); 105 } 106 return 0; 107 }

?

轉載于:https://www.cnblogs.com/WABoss/p/5293626.html

總結

以上是生活随笔為你收集整理的HDU3247 Resource Archiver（AC自动机+BFS+DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。