hdoj3247

佚名 6年前 (2019-04-26) 随笔 369人围观抢沙发百度已收录

注意fail时怎么走。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cstring>
#include <map>
#include <queue>
#include <set>
#include <cassert>
#include <stack>
#include <bitset>
#define mkp make_pair
using namespace std;
const double EPS=1e-12;
typedef long long lon;
const lon SZ=60010,SSZ=12,APB=2,one=1;
const lon INF=0x7FFFFFFF,mod=1000000007;
lon n,m,mk[SZ],nex[SZ][APB],fail[SZ];
int cnt,endpos[SSZ],dst[SSZ][SSZ];
int dtb[SZ],dp[1030][SSZ],len[SSZ];
int ctn[SSZ][SSZ];
char ch[SZ];
string str[SSZ];

void add(int type,int id)
{
    int cur=0;
    for(int i=1;ch[i];++i)
    {
        int c=ch[i]-'0';
        if(!nex[cur][c])nex[cur][c]=++cnt;
        cur=nex[cur][c];
    }
    if(type)mk[cur]=1;
    else endpos[id]=cur;
}

void build()
{
    queue<int> q;
    q.push(0);
    for(;q.size();)
    {
        int fr=q.front();
        q.pop();
        for(int i=0;i<APB;++i)
        {
            int t=nex[fr][i];
            if(t)
            {
                if(!fr)fail[t]=0;
                else
                {
                    int u=fail[fr];
                    for(;u&&!nex[u][i];u=fail[u]);
                    u=nex[u][i];
                    fail[t]=u;
                    mk[t]|=mk[u];
                }
                q.push(t);
            }
        }
    }
}

void bfs(int x)
{
    dtb[x]=0;
    queue<int> q;
    q.push(x);
    for(;q.size();)
    {
        int fr=q.front();
        q.pop();
        for(int i=0;i<APB;++i)
        {
            int t=nex[fr][i];
            if(t)
            {
                if(dtb[t]>dtb[fr]+1&&!mk[t])
                {
                    q.push(t);
                    dtb[t]=dtb[fr]+1;
                }
            }
            else
            {
                int u=fail[fr];
                for(;u&&!nex[u][i];u=fail[u]);
                t=nex[u][i];
                if(dtb[t]>dtb[fr]+1&&!mk[t])
                {
                    q.push(t);
                    dtb[t]=dtb[fr]+1;
                }
            }
        }
    }
}

void init()
{
    for(int i=0;i<n;++i)
    {
        //cin>>ch+1;
        scanf(" %s",ch+1);
        len[i]=strlen(ch+1);
        add(0,i);
        string tmp(ch+1);
        str[i]=tmp;
    }
    for(int i=0;i<m;++i)
    {
        scanf(" %s",ch+1);
        add(1,-1);
    }
    build();
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<=cnt;++j)
        dtb[j]=INF/2;
        int sta=0;
        bfs(endpos[i]);
        for(int j=0;j<n;++j)
        {
            dst[i][j]=dtb[endpos[j]];
        }
    }
}

int dfs(int sta,int last)
{
    //cout<<sta<<" "<<last<<endl;
    if(dp[sta][last])return dp[sta][last];
    else
    {
        int res=INF/2;
        for(int i=0;i<n;++i)
        {
            if(ctn[last][i]&&(sta&(1<<i)))sta^=1<<i;
        }
        if(sta==0)return len[last];
        for(int i=0;i<n;++i)
        {
            if(sta&(1<<i))
            {
                res=min(res,dfs(sta,i)+dst[i][last]);
            }
        }
        return dp[sta][last]=res;
    }
}

void work()
{
    for(int i=0;i<n;++i)
    {
        dp[1<<i][i]=len[i];
    }
    int res=INF/2;
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<n;++j)
        {
            if(str[i].find(str[j])!=-1)ctn[i][j]=1;
        }
    }
//    for(int i=0;i<n;++i)
//    {
//        for(int j=0;j<n;++j)
//        {
//            cout<<ctn[i][j]<<" ";
//        }cout<<endl;
//    }
    for(int i=0;i<n;++i)
    {
        res=min(res,dfs((1<<n)-1,i));
        //cout<<"i: "<<dfs((1<<n)-1,i)<<" "<<dst[0][1]<<" "<<dst[1][0]<<endl;
    }
    cout<<res<<endl;
}

void release()
{
    for(int i=0;i<=cnt;++i)
    {
        mk[i]=0;
        memset(nex[i],0,sizeof(nex[i]));
        fail[i]=0;    
    }
    cnt=0;
    for(int i=0;i<(1<<n);++i)
    {
        memset(dp[i],0,sizeof(dp[i]));
    }
}

int main()
{
    //std::ios::sync_with_stdio(0);
    //freopen("d:\\1.txt","r",stdin);
    int casenum;
    //memset(bel,-1,sizeof(bel));
    //cin>>casenum;
    //cout<<casenum<<endl;
    //for(int time=1;time<=casenum;++time)
    for(int time=1;cin>>n>>m,n;++time)
    {
        init();
        work();
        release();
    }
    return 0;
}