[题解] P3082 [USACO13MAR]Necklace G

¶凉笙 · 2021-07-18 11:15:53 · 题解

[题解] [USACO13MAR]Necklace G

传送门

前置知识

• AC 自动机。

如果你不会，可以看看 这篇文章（我不会告诉你我是来推销博客的。

请确保您已经学会 AC 自动机。

解题报告

对于题中的两个字符串，显然奶牛的名字是模式串，我们先把它插入到 AC 自动机中。

没有什么正确的贪心做法，因此考虑 DP。

设题目中项链的字符串为 S，奶牛的名字为 S'， f[i,j] 表示已经考虑了 S 的前 i 个字符，在 AC 自动机上对应的第 j 个结点的最大保留长度。

• 设 nxt 为上一个结点 j 的 i 指针，如果指向的不是 S' 结束的位置，那么 f[i,nxt]=max(f[i,nxt],f[i-1][j]+1) 。

• 同样地，如果当前位置不是 S' 的结束位置，那么 f[i,j]=max(f[i,j],f[i-1][j])。

最后答案取个 max，用总长度减去就好了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template <typename T>
inline T read(){
    T x=0;char ch=getchar();bool fl=false;
    while(!isdigit(ch)){if(ch=='-')fl=true;ch=getchar();}
    while(isdigit(ch)){
        x=(x<<3)+(x<<1)+(ch^48);ch=getchar();
    }
    return fl?-x:x;
}
#include <queue>
const int maxn = 1000 + 10;
int f[maxn*10][maxn];
namespace AC{
int t[maxn][26],fail[maxn],end[maxn],cnt=0;
void insert(char *s){
    int u=0;
    for(int i=1;s[i];i++){
        if(!t[u][s[i]-'a'])t[u][s[i]-'a']=++cnt;
        u=t[u][s[i]-'a'];
    }
    end[u]=1;
}
queue<int> q;
void build(){
    for(int i=0;i<26;i++)if(t[0][i])q.push(t[0][i]);
    while(q.size()){
        int u=q.front();q.pop();
        for(int i=0;i<26;i++){
            if(t[u][i])fail[t[u][i]]=t[fail[u]][i],q.push(t[u][i]);
            else t[u][i]=t[fail[u]][i];
        }
    }
}
}
using namespace AC;
char s[maxn],T[maxn*10];
int main(){
    cin>>T+1>>s+1;
    insert(s);build();
    int len=strlen(T+1);
    for(int i=1;i<=len;i++){
        for(int j=0;j<=cnt;j++){
            if(!end[t[j][T[i]-'a']])
                f[i][t[j][T[i]-'a']]=max(f[i][t[j][T[i]-'a']],f[i-1][j]+1);
            if(!end[j])
                f[i][j]=max(f[i][j],f[i-1][j]);
        }
    }
    int ans=0;
    for(int i=0;i<=cnt;i++)ans=max(ans,f[len][i]);
    printf("%d\n",len-ans);
    return 0;
}

小结

个人认为 AC 自动机只是简化了 DP 的过程，并且便于理解。

本质上和其它题解的线性 DP 还是一样的。