HDU 3247 Resource Archiver（AC自动机 + 状压DP + bfs预处理）题解

题意：目标串n( <= 10)个，病毒串m( < 1000)个，问包含所有目标串无病毒串的最小长度

思路：貌似是个简单的状压DP + AC自动机，但是发现dp[1 << n][5e4]根本开不出那么多空间，似乎GG。但是我们仔细想一下就能发现，既然要包含所有目标串的最小长度，那必然这个串就是只有目标串叠加组成的，只是在叠加的过程中我们不能混入病毒串。所以其实Trie树上有用的点最多就10个，我们只要处理出所有目标串之间“最小有效转化”就行了，那么空间为dp[1 << n][10]。

处理目标串之间“最小有效转化”可以直接暴力BFS，build标记后在Trie树上跑。

代码：

#include<set>

#include<map>

#include<queue>

#include<cmath>

#include<string>

#include<cstdio>

#include<vector>

#include<cstring>

#include <iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int maxn = 6e4 + 5;

const int M = 50 + 5;

const ull seed = 131;

const int INF = 0x3f3f3f3f;

const int MOD = 20090717;

int n, m;

int dp[1 << 10 + 5][20];

int point[1015];

int length[1015];

int dis[20][20];

int vis[maxn];

int tot;

struct Node{

    int u, step;

};

struct Aho{

    struct state{

        int next[2];

        int fail, cnt, is;

    }node[maxn];

    int size;

    queue<int> q;

    void init(){

        size = 0;

        newtrie();

        while(!q.empty()) q.pop();

    }

    int newtrie(){

        memset(node[size].next, 0, sizeof(node[size].next));

        node[size].cnt = node[size].fail = 0;

        return size++;

    }

    void insert(char *s, int id){

        int len = strlen(s);

        int now = 0;

        for(int i = 0; i < len; i++){

            int c = s[i] - '0';

            if(node[now].next[c] == 0){

                node[now].next[c] = newtrie();

            }

            now = node[now].next[c];

        }

        node[now].cnt = 1 << id;

        node[now].is = tot;

        length[tot] = len;

        point[tot++] = now;

    }

    void build(){

        node[0].fail = -1;

        q.push(0);

        while(!q.empty()){

            int u = q.front();

            q.pop();

            if(node[node[u].fail].cnt && u) node[u].cnt |= node[node[u].fail].cnt;

            for(int i = 0; i < 2; i++){

                if(!node[u].next[i]){

                    if(u == 0)

                        node[u].next[i] = 0;

                    else

                        node[u].next[i] = node[node[u].fail].next[i];

                }

                else{

                    if(u == 0) node[node[u].next[i]].fail = 0;

                    else{

                        int v = node[u].fail;

                        while(v != -1){

                            if(node[v].next[i]){

                                node[node[u].next[i]].fail = node[v].next[i];

                                break;

                            }

                            v = node[v].fail;

                        }

                        if(v == -1) node[node[u].next[i]].fail = 0;

                    }

                    q.push(node[u].next[i]);

                }

            }

        }

    }

    void bfs(int x){

        queue<Node> Q;

        while(!Q.empty()) Q.pop();

        memset(vis, 0, sizeof(vis));

        dis[x][x] = 0;

        vis[point[x]] = 1;

        Node a, b;

        a.u = point[x], a.step = 0;

        Q.push(a);

        while(!Q.empty()){

            a = Q.front();

            Q.pop();

            for(int i = 0; i < 2; i++){

                int v = node[a.u].next[i];

                if(vis[v]) continue;

                vis[v] = 1;

                if(node[v].cnt < (1 << 20)){

                    if(node[v].cnt) dis[x][node[v].is] = a.step + 1;

                    b.u = v, b.step = a.step + 1;

                    Q.push(b);

                }

            }

        }

    }

    void query(){

        for(int i = 0; i < (1 << n); i++)

            for(int j = 0; j < n; j++)

                dp[i][j] = INF;

        for(int i = 0; i < n; i++){

            dp[node[point[i]].cnt][i] = length[i];

        }

        for(int i = 0; i < (1 << n); i++){

            for(int j = 0; j < n; j++){

                if(dp[i][j] == INF) continue;

                for(int k = 0; k < n; k++){

                    int arr = node[point[k]].cnt;

//                    if(arr & i) continue;

                    dp[i | arr][k] = min(dp[i | arr][k], dp[i][j] + dis[j][k]);

                }

            }

        }

        int ans = INF;

        for(int i = 0; i < n; i++){

            ans = min(ans, dp[(1 << n) - 1][i]);

        }

        printf("%d\n", ans);

    }

}ac;

char s[1005];

int main(){

    int ca = 1;

    while(~scanf("%d%d", &n, &m) && n + m){

        tot = 0;

        ac.init();

        for(int i = 0; i < n; i++){

            scanf("%s", s);

            ac.insert(s, i);

        }

        for(int i = 0; i < m; i++){

            scanf("%s", s);

            ac.insert(s, 20);

        }

        ac.build();

        for(int i = 0; i < n; i++)

            ac.bfs(i);

        ac.query();

    }

    return 0;

}

/*

2 1

1110

0111

101

1 1

1

0

*/

巴特西

HDU 3247 Resource Archiver（AC自动机 + 状压DP + bfs预处理）题解

最新文章

热门文章