[bzoj1195][HNOI2006]最短母串_动态规划_状压dp

时间：2023-03-09 18:36:54
[bzoj1195][HNOI2006]最短母串_动态规划_状压dp

最短母串 bzoj-1195 HNOI-2006

题目大意：给一个包含n个字符串的字符集，求一个字典序最小的字符串使得字符集中所有的串都是该串的子串。

注释：$1\le n\le 12$，$1\le max length \le 50$。

想法：刚开始在那里AC自动机半天，然后瞅了一眼数据范围... ...状压吧兄弟！！

首先，我们先做一些预处理：把可以被字符集中串包含的串都删掉；求出两个字符串连接后的长度（这个预处理暴力即可），设merge[i][j]表示串i和串j合并后的长度。

状态：dp[s][i]表示这个串已经包含了s状态的字符串且紧跟着的串是i的最短长度。

转移：dp[s][i]=min{dp[s^(1<<(j+1))][j]+merge[i][j]-length(j)};

最后，附上丑陋的代码... ...

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

using namespace std;

const int INF=0x3f3f3f3f;

const int mxn=61;

int n;

struct bind

{

    char s[605];

    int len;

    bool operator < (const bind y) const

	{

        if(len!=y.len)return len<y.len;

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

            if(s[i]!=y.s[i])return s[i]<y.s[i];

        return 0;

    }

}f[1<<12][12],s[12];

int c[13][13];

bool ban[mxn];

bool ovl(int i,int j)

{

    if(s[i].len<s[j].len)return 0;

    char *p=strstr(s[i].s,s[j].s);

    if(p==NULL)return 0;

    return 1;

}

int clc(int x,int y)

{

    bool flag=0;

    for(int i=max(0,s[x].len-s[y].len);i<s[x].len;i++)

	{

        flag=1;

        for(int j=i;j<s[x].len;j++)

            if(s[x].s[j]!=s[y].s[j-i]){flag=0;break;}

        if(flag)return s[x].len-i;

    }

    return 0;

}

bind merge(int S,int u,int v)

{

    bind tmp=f[S][u];

    strcat(tmp.s,s[v].s+c[u][v]);

    tmp.len=f[S][u].len-c[u][v]+s[v].len;

    return tmp;

}

void Dp()

{

    int i,j,ed=(1<<n)-1;

    for(i=0;i<=ed;i++)

        for(j=0;j<n;j++)f[i][j].len=INF;

    for(i=0;i<n;i++)f[1<<i][i]=s[i];

    for(i=1;i<=ed;i++)

	{

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

		{

            if((i>>j)&1)

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

				{

                    if((i>>k)&1) continue;

                    bind tmp=merge(i,j,k);

                    if(tmp<f[i|(1<<k)][k])f[i|(1<<k)][k]=tmp;

                }

        }

    }

}

int main()

{

    scanf("%d",&n);

    for(int i=0;i<n;i++)scanf("%s",s[i].s),s[i].len=strlen(s[i].s);

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

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

            if(i!=j && ovl(i,j) && !ban[i])ban[j]=1;

    int cnt=0;

    for(int i=0;i<n;i++)if(!ban[i])s[cnt++]=s[i];

    n=cnt;

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

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

            if(i!=j)c[i][j]=clc(i,j);

    Dp();

    int ans=0,ed=(1<<n)-1;

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

        if(f[ed][i]<f[ed][ans])ans=i;

    printf("%s",f[ed][ans].s);

    return 0;

}

小结：看到了数据做题是一种解题想法，但是考试的时候看数据范围猜复杂度我tm就没成功过... ...

相关文章