首页 > 代码库 > HDU 3247 Resource Archiver AC自动机 + bfs + 状态压缩dp
HDU 3247 Resource Archiver AC自动机 + bfs + 状态压缩dp
题意：给定你n个文本串 ，m个模式串，怎么构造最短的新的文本串使得这个新的文本串包含n个文本串的所有信息且文本串的长度最短且不包含模式串。
解题思路：这里看题解撸的，首先我们算出两两文本串的距离（end数组标记文本和模式串的值不同，利用这个进行bfs算出两两之间的最短距离，注意到这里模式串的end是不能走到的。这里也不需要松弛操作），然后因为n只有10这么大，所以我们可以状态压缩 ，dp[i][j] 表示 压缩后状态为 i（二进制压缩，每i位表示第i个是否在）且 以j结尾的文本串的最小花费。这样去dp即可。
解题代码：
1 // File Name: temp.cpp 2 // Author: darkdream 3 // Created Time: 2014年09月11日 星期四 15时18分4秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #include<queue> 25 #define LL long long 26 #define maxn 60002 27 #define INF 0x3f3f3f3f 28 using namespace std; 29 int n,m; 30 struct Trie 31 { 32 int next[maxn][2],fail[maxn],end[maxn]; 33 int root, L; 34 int newnode() 35 { 36 memset(next[L],-1,sizeof(next[L])); 37 end[L++] = 0 ; 38 return L-1; 39 } 40 void init() 41 { 42 L = 0 ; 43 root = newnode(); 44 } 45 void insert(char buf[],int status) 46 { 47 int now = root; 48 int len = strlen(buf); 49 for(int i = 0 ;i < len ;i ++) 50 { 51 if(next[now][buf[i] - ‘0‘] == -1) 52 next[now][buf[i] - ‘0‘] = newnode(); 53 now = next[now][buf[i] - ‘0‘]; 54 } 55 end[now] = status; 56 } 57 void build() 58 { 59 queue<int> Q; 60 fail[root] = root; 61 for(int i = 0;i < 2;i ++) 62 { 63 if(next[root][i] == -1) 64 { 65 next[root][i] = root; //指向root 是没有问题的，我们主要是通过end 数组对个数进行计数的。 66 }else{ 67 fail[next[root][i]] = root; 68 Q.push(next[root][i]); 69 } 70 } 71 while(!Q.empty()) 72 { 73 int now = Q.front(); 74 Q.pop(); 75 for(int i = 0 ;i < 2;i ++) 76 { 77 if(next[now][i] == -1) 78 { 79 next[now][i] = next[fail[now]][i]; 80 } 81 else{ 82 fail[next[now][i]] = next[fail[now]][i]; 83 Q.push(next[now][i]); 84 } 85 } 86 } 87 } 88 int g[11][11]; 89 int dp[1025][11]; 90 int cnt; 91 int pos[11]; 92 int dis[60010]; 93 void bfs(int k )// bfs 因为是直接 bfs 所以没有松弛操作 94 { 95 queue<int> q; 96 memset(dis,-1,sizeof(dis)); 97 dis[pos[k]] = 0 ; 98 q.push(pos[k]); 99 while(!q.empty())100 {101 int now = q.front();102 q.pop();103 for(int i = 0 ;i < 2; i ++)104 {105 int tmp = next[now][i];106 if(dis[tmp] < 0 && end[tmp] >= 0 )107 {108 dis[tmp] = dis[now] +1;109 q.push(tmp);110 }111 }112 }113 for(int i = 0 ;i < cnt; i ++)114 g[k][i] = dis[pos[i]];115 }116 int query()117 {118 119 pos[0] = 0;120 cnt = 1;121 for(int i = 0;i < L;i++)122 if(end[i] > 0)123 pos[cnt++] = i;124 for(int i = 0; i < cnt;i++)125 bfs(i);126 127 for(int i = 0;i < (1<<n);i++)128 for(int j = 0;j < cnt;j++)129 dp[i][j] = INF;130 dp[0][0] = 0; //131 for(int i = 0;i <(1<<n);i++)132 for(int j = 0;j < cnt;j++)133 if(dp[i][j]<INF)134 {135 for(int k = 0;k < cnt;k++)136 {137 if(g[j][k] < 0)continue;138 if( j == k)continue;139 dp[i|end[pos[k]]][k] = min(dp[i|end[pos[k]]][k],dp[i][j]+g[j][k]);140 }141 }142 int ans = INF;143 for(int j = 0;j < cnt;j++)144 ans = min(ans,dp[(1<<n)-1][j]);145 return ans;146 }147 };148 Trie ac;149 char str[50005];150 int main(){151 while(scanf("%d %d",&n,&m ) != EOF)152 {153 if(n == 0 && m == 0 )154 break;155 ac.init();156 for(int i = 0;i < n;i ++)157 {158 scanf("%s",str);159 ac.insert(str,1<<i);160 }161 for(int i = 1;i <= m;i ++)162 {163 scanf("%s",str);164 ac.insert(str,-1);165 }166 ac.build();167 168 printf("%d\n",ac.query());169 }170 return 0;171 }
HDU 3247 Resource Archiver AC自动机 + bfs + 状态压缩dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。