『AFO-OI题解』洛谷P3502 [POI2010]CHO-Hamsters

首先登出原题位置

好了，进入正题（废话）

本来这题是***联赛模拟***的一道T3，然而在联赛前一天被我找到了原题23333...

话不多说讲做* _ *

首先

互不包含是一个很重要的前提，这说明n个字符串在答案串S中的m次出现一定会依次出现（指的是$m$次出现的首位置一定会不同，但m次出现可能会存在重叠）

那么我们预先处理出来每个串接在另一个串的后面所需要新添加的字符数量，记为dis[i][j]。这里涉及的的字符串匹配，官方正解给出的是AC自动机。然而我这个小蒟蒻不会呀，所以就用的是KMP算法，时间复杂度是$O(\sum\sum(len(i)+len(j)))O(∑∑(len(i)+len(j)))$，把式子化一下会发现复杂度就是$O(nO(n总串长))$，所以还是能过的。

如果有了dis[i][j]，那么应该不难想到一个$O(n^2m)O(n2m)$的DP式。我们设dp[t][i]表示总串中已经出现了t个字符串，且最后一个出现的串是i号串的最小代价，代码如下：

for (int i=1;i<=n;i++)
        dp[1][i]=len[i];
for (int t=2;t<=m;t++)
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            dp[t][i]=min(dp[t][i],dp[t-1][j]+dis[j][i]);

最终的答案就是$min{dp[m][i]}$。

然而我们发现$m$很大，怎么办呢/ - ^ - /

上面的那个式子是不是有点眼熟？有点像$FloyedFloyed$？

我们可以这样转化一下模型：把每个字符视为一个点，一次转移相当于从一个点走到另一个点，最终的答案就是问你总共走m次的最小距离。边界情况：第一个串的代价总是等于串长，所以我们新建一个0号点，另$dis[0][i]=len[i]，dis[i][0]=dis[0][0]=INF$，那么在经过$m$次转移之后，最终答案就是$min{Ans[0][i]}$。

这样，每一次转移就相当于跑一次$O(n^3)O(n 3)$的$FloyedFloyed$，$m$怎么办？矩阵加速优化！

至此这题应该就讲完了，具体代码实现应该还是不难的^-

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
const int _ = 205;
const ll INF = 1e18;
char s[_][100005];
int n,m,len[_],next[_][100005];
ll ans=INF;
struct matrix
{
    ll f[205][205];
    matrix operator * (matrix &b)
        {
            matrix c;
            memset(c.f,63,sizeof(c.f));
            for (int i=0;i<=n;i++)
                for (int j=0;j<=n;j++)
                    for (int k=0;k<=n;k++)
                        c.f[i][k]=min(c.f[i][k],f[i][j]+b.f[j][k]);//一遍Floyed,和矩阵乘法类似但有不同
            return c;
        }
}Tra,Ans;//状态矩阵Ans,转移矩阵Tra
int main()
{
    //freopen("hamsters.in","r",stdin);
    //freopen("hamsters.out","w",stdout);
    scanf("%d %d\n",&n,&m);
    for (int i=1;i<=n;i++)
        scanf("%s",s[i]+1),len[i]=strlen(s[i]+1);
    for (int t=1;t<=n;t++)
    {
        int j=0;
        for (int i=2;i<=len[t];i++)
        {
            while (j&&s[t][j+1]!=s[t][i]) j=next[t][j];//预处理next数组
            if (s[t][j+1]==s[t][i]) j++;
            next[t][i]=j;
        }
    }
    Tra.f[0][0]=INF;//边界情况
    for (int x=1;x<=n;x++)
    {
        Tra.f[0][x]=len[x];Tra.f[x][0]=INF;//边界情况
        for (int y=1;y<=n;y++)
        {
            int j=0;
            for (int i=2;i<=len[x];i++)
            {
                while (j&&s[y][j+1]!=s[x][i]) j=next[y][j];
                if (s[y][j+1]==s[x][i]) j++;
                if (i==len[x]) Tra.f[x][y]=len[y]-j;
            }
        }
    }
    for (int i=0;i<=n;i++)
        for (int j=0;j<=n;j++)
            Ans.f[i][j]=Tra.f[i][j];
    for (m--;m;m>>=1)//Ans的初始状态就已经有一次转移了，所以m--
    {
        if (m&1) Ans=Ans*Tra;
        Tra=Tra*Tra;
    }
    for (int i=1;i<=n;i++)
        ans=min(ans,Ans.f[0][i]);
    return printf("%lld\n",ans),0
}
//完结撒花！！！

洛谷千万人，守信第一人，复制原代码，提交两行泪！（有防抄袭