Blackops

初心易得，始终难守

0%

HDU 3247 Resource Archiver（AC自动机+BFS+状压DP）

发表于 更新于 分类于 ， ，

Resource Archiver

Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 100000/100000 K (Java/Others)
Total Submission(s): 2925 Accepted Submission(s): 950

Problem Description
Great! Your new software is almost finished! The only thing left to do is archiving all your n resource files into a big one.
Wait a minute… you realized that it isn’t as easy as you thought. Think about the virus killers. They’ll find your software suspicious, if your software contains one of the m predefined virus codes. You absolutely don’t want this to happen.
Technically, resource files and virus codes are merely 01 strings. You’ve already convinced yourself that none of the resource strings contain a virus code, but if you make the archive arbitrarily, virus codes can still be found somewhere.
Here comes your task (formally): design a 01 string that contains all your resources (their occurrences can overlap), but none of the virus codes. To make your software smaller in size, the string should be as short as possible.

Input
There will be at most 10 test cases, each begins with two integers in a single line: n and m (2 <= n <= 10, 1 <= m <= 1000). The next n lines contain the resources, one in each line. The next m lines contain the virus codes, one in each line. The resources and virus codes are all non-empty 01 strings without spaces inside. Each resource is at most 1000 characters long. The total length of all virus codes is at most 50000. The input ends with n = m = 0.

Output
For each test case, print the length of shortest string.

Sample Input
2 2
1110
0111
101
1001
0 0

Sample Output
5

题目链接：HDU 3247
题意就是构造最短的串使得不仅覆盖了n个resource串，还不能含有m个病毒串,这题是看kuangbin大佬博客才会写的，由于只有10个resource串，因此把resource和virus插入字典树并就建立AC自动机，由于要求最小的长度，因此只有安全节点有用的，最多只有$11$个，显然virus串的结束点都是危险节点，赋值为$-1$，其他resourse串用状压表示，最后建立AC自动机的时候传递一下fail指针的状态就可以了，然后说一下DP，用$dp[i][j]$表示当前走到了第$i$个安全节点节点，包含的resourse串的二进制状态为$j$，考虑合法性问题，$dp$数组要初始化为$\infty$
转移方程就是：

为什么是这样的呢，因为题目要求包含所有的串，那么我们就BFS的时候只走非危险节点，然后把到各个resourse串末尾节点的距离表示出来，其距离就是所需增加的长度，然后$dis$数组就这样BFS预处理出来就优化了转移时间
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <bitset>
#include <string>
#include <stack>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 60010;
struct Trie
{
    int nxt[2];
    int fail, flag;
    void init()
    {
        for (int i = 0; i < 2; ++i)
            nxt[i] = -1;
        fail = flag = 0;
    }
} L[N];
int sz;
int dp[11][1 << 10];
int G[11][11], d[N], st[11], cnt;
queue<int>Q;
char s[N];

void init()
{
    CLR(dp, INF);
    cnt = 0;
    CLR(G, INF);
}
void BFS(int x)
{
    while (!Q.empty())
        Q.pop();
    CLR(d, INF);
    Q.push(st[x]);
    d[st[x]] = 0;
    while (!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        for (int i = 0; i < 2; ++i)
        {
            int v = L[u].nxt[i];
            if (d[v] > d[u] + 1 && L[v].flag >= 0)
            {
                d[v] = d[u] + 1;
                Q.push(v);
            }
        }
    }
    for (int i = 0; i < cnt; ++i)
        G[x][i] = d[st[i]];
}
namespace ac
{
    void init()
    {
        sz = 0;
        L[sz++].init();
    }
    inline int newnode()
    {
        L[sz].init();
        return sz++;
    }
    void ins(char s[], int len, int x)
    {
        int u = 0;
        for (int i = 0; i < len; ++i)
        {
            int v = s[i] - '0';
            if (L[u].nxt[v] == -1)
                L[u].nxt[v] = newnode();
            u = L[u].nxt[v];
        }
        if (x != -1 && L[u].flag != -1)
            L[u].flag |= (1 << x);
        else
            L[u].flag = -1;
    }
    void build()
    {
        queue<int>Q;
        L[0].fail = 0;
        for (int i = 0; i < 2; ++i)
        {
            int &v = L[0].nxt[i];
            if (v == -1)
                v = 0;
            else
            {
                L[v].fail = 0;
                Q.push(v);
            }
        }
        while (!Q.empty())
        {
            int u = Q.front();
            Q.pop();
            int uf = L[u].fail;
            if (L[uf].flag == -1)
                L[u].flag = -1;
            else
                L[u].flag |= L[uf].flag;
            for (int i = 0; i < 2; ++i)
            {
                int &v = L[u].nxt[i];
                if (v == -1)
                    v = L[uf].nxt[i];
                else
                {
                    L[v].fail = L[uf].nxt[i];
                    Q.push(v);
                }
            }
        }
    }
}
int main(void)
{
    int n, m, i, j, k;
    while (~scanf("%d%d", &n, &m) && (n || m))
    {
        ac::init();
        init();
        for (i = 0; i < n; ++i)
        {
            scanf("%s", s);
            ac::ins(s, strlen(s), i);
        }
        for (i = 0; i < m; ++i)
        {
            scanf("%s", s);
            ac::ins(s, strlen(s), -1);
        }
        ac::build();
        st[cnt++] = 0;
        for (i = 0; i < sz; ++i)
            if (L[i].flag > 0)
                st[cnt++] = i;
        for (i = 0; i < cnt; ++i)
            BFS(i);
        int R = 1 << n;
        dp[0][0] = 0;
        for (i = 0; i < R; ++i)
        {
            for (j = 0; j < cnt; ++j)
            {
                if (dp[j][i] != INF)
                {
                    for (k = 0; k < cnt; ++k)
                    {
                        if (j == k || G[j][k] >= INF)
                            continue;
                        dp[k][i | L[st[k]].flag] = min(dp[k][i | L[st[k]].flag], dp[j][i] + G[j][k]);
                    }
                }
            }
        }
        int ans = INF;
        for (i = 0; i < cnt; ++i)
            ans = min(ans, dp[i][R - 1]);
        printf("%d\n", ans);
    }
    return 0;
}