題目鏈接：點擊查看

題目大意：給出 n 個目標串和 m 個病毒串，要求構(gòu)造出一個長度最短的，且包含全部 n 個目標串，但是不能包含任意一個病毒串的01字符串，輸出其最短長度

題目分析：比較綜合的一道題目了，以為是涉及到目標串和病毒串之間的關(guān)系，所以讀完題目后不難想到先將這些字符串都扔到AC自動機里去，因為 n 非常小，所以可以考慮狀態(tài)壓縮，于是最初的想法就是壯壓dp直接轉(zhuǎn)移，dp[ state1 ][ state2 ] 代表著含有目標串狀態(tài)為state1，且在AC自動機中的狀態(tài)為state2時的最短長度，但非常遺憾的是，整個dp轉(zhuǎn)移的時間復(fù)雜度達到了1024*50000*2，不出意外的話是會TLE的，所以我們必須想辦法優(yōu)化，稍微想一下的話不難發(fā)現(xiàn)，AC自動機中絕大部分的字符串都是病毒串的，也就是沒有作用的結(jié)點，我們真正會用到的也只有那 n<=10 個結(jié)點，所以在建好AC自動機后，將可以代表目標串的結(jié)點單獨拿出，因為之前的轉(zhuǎn)移方程是：（設(shè) i 為目標串的狀態(tài)，j 為AC自動機的狀態(tài)，nj 為接下來的狀態(tài)，id[ i ]為AC自動機內(nèi)結(jié)點 i 所代表的目標串狀態(tài)）

dp[ i | id[ nj ] ][ nj ] = min( dp[ i | id[ nj ] ][ nj ] , dp[ i ][ j ] + 1 )

而現(xiàn)在的狀態(tài)轉(zhuǎn)移就變成了：

dp[ i | id[ nj ] ][ nj ] = min( dp[ i | id[ nj ] ][ nj ] , dp[ i ][ j ] + dis[ i ][ nj ]?)

其中dis[ i ][ j ]代表著從狀態(tài) i 到狀態(tài) j 所需要添加的最少字符，到這里，我們就可以發(fā)現(xiàn)，因為dis[ i ][ j ]可以用bfs預(yù)處理得出，這樣總的時間復(fù)雜度也就下降為了 1024*10*10 了

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e5+100;char s[N];int fail[N],id[N],trie[N][2],cnt;void insert_word(int _id) {int len=strlen(s);int pos=0;for(int i=0;i<len;i++){int to=s[i]-'0';if(!trie[pos][to])trie[pos][to]=++cnt;pos=trie[pos][to];}id[pos]=_id; }void getfail() {queue<int>q;for(int i=0;i<2;i++){if(trie[0][i]){fail[trie[0][i]]=0;q.push(trie[0][i]);}}while(!q.empty()){int cur=q.front();q.pop();if(id[fail[cur]]<0)id[cur]=-1;elseid[cur]|=id[fail[cur]];for(int i=0;i<2;i++){if(trie[cur][i]){fail[trie[cur][i]]=trie[fail[cur]][i];q.push(trie[cur][i]);}elsetrie[cur][i]=trie[fail[cur]][i];}} }vector<int>state;int dis[N],maze[15][15],dp[(1<<10)+100][15];void bfs(int pos) {memset(dis,inf,sizeof(dis));queue<int>q;q.push(state[pos]);dis[state[pos]]=0;while(q.size()){int cur=q.front();q.pop();for(int i=0;i<2;i++){int nj=trie[cur][i];if(id[nj]<0)continue;if(dis[nj]>dis[cur]+1){dis[nj]=dis[cur]+1;q.push(nj);}}}for(int i=0;i<state.size();i++)maze[pos][i]=dis[state[i]]; }void init() {cnt=0;memset(id,0,sizeof(id));memset(trie,0,sizeof(trie));state.clear(); }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,m;while(scanf("%d%d",&n,&m)!=EOF&&n+m){init();for(int i=0;i<n;i++){scanf("%s",s);insert_word((1<<i));}while(m--){scanf("%s",s);insert_word(-1);}getfail();state.push_back(0);for(int i=0;i<=cnt;i++)if(id[i]>0)state.push_back(i);for(int i=0;i<state.size();i++)bfs(i);memset(dp,inf,sizeof(dp));dp[0][0]=0;for(int i=0;i<(1<<n);i++){for(int j=0;j<state.size();j++){for(int k=0;k<state.size();k++){if(dp[i][j]!=inf){if(maze[j][k]==inf)continue;if(j==k)continue;dp[i|id[state[k]]][k]=min(dp[i|id[state[k]]][k],dp[i][j]+maze[j][k]);}}}}int ans=inf;for(int i=0;i<state.size();i++)ans=min(ans,dp[(1<<n)-1][i]);printf("%d\n",ans); }return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU - 3247 Resource Archiver(AC自动机+状压dp+bfs)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。