Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

hdu多校第一场 1006 (hdu6583)Typewriter dp/后缀自动机

Isakovsky 2019-07-25 19:33:00 阅读数:18 评论数:0 点赞数:0 收藏数:0

题意:

有个打字机,在当前字符串后新加一个字花费p,把当前字符串的一个连续子串拷贝到当前字符串的末尾花费q,给定一个字符串,求用打字机打出这个字符串的最小花费。

题解:

容易想到用dp

记dp[i]为打出前i个字符的最小花费,对于每个i,令

A=dp[i-1]+p 

B=dp[j]+q 其中j为最小的,使得s[j+1~i]是s[1~j]的连续子串的值

其实就是,把这个字符串咔嚓切一刀,看后面的部分是不是前面部分的子串,如果不是,就把切的地方向后挪,前面的部分是原串,后面的部分是模式串。

dp[i]=min(A,B)

假如在i=k的时候已经找到了这么一个最优切分点j,那么在讨论i=k+1的时候,这个最优切分点要么就是原来的j,要么就需要把这个j向后挪。

为啥,因为j已经是令原串最短的切分点了,现在你还要往模式串后面加东西,原串不可能更短,只能更长。

注意,在j向后移动的过程中,出现了将模式串的第一位砍掉的操作,那么问题来了,有没有一种数据结构,支持这种将模式串的前面砍掉的操作呢?

后缀自动机。后缀自动机上一个节点代表多个连续子串,其中一个最长,剩下的都是这个最长的连续子串的后缀,父节点又是子节点的后缀,那么,对于某个自动机上的连续子串,把它最前面一位砍掉,要么它还停留在原来的节点上,要么它转移到了父节点上。

后缀自动机增量构造复杂度O(1),状态转移复杂度O(1)

总时间复杂度O(n)

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define maxn=200005;
#define kind=;
struct state
{
    state *Next[kind],*link;
    int len;
    state()
    {
        link=;
        len=;
        memset(Next,,sizeof(Next));
    }
};
int sz;
state st[maxn*+];
inline state* newnode(int len = )
{
    memset(st[sz].Next,,sizeof(st[sz].Next));
    st[sz].link=;
    st[sz].len=len;
    return &st[sz++];
}
state *root,*last;
void extend(int w)
{
    state* p=last;
    state* cur=newnode(p->len+);
    while(p&&p->Next[w]==)
    {
        p->Next[w]=cur;
        p=p->link;
    }
    if(p)
    {
        state* q=p->Next[w];
        if(p->len+==q->len)
            cur->link=q;
        else
        {
            state* clone=newnode(p->len+);
            memcpy(clone->Next,q->Next,sizeof(q->Next));
            clone->link=q->link;
            q->link=clone;
            cur->link=clone;
            while(p&&p->Next[w]==q)
            {
                p->Next[w]=clone;
                p=p->link;
            }
        }
    }
    else cur->link=root;
    last=cur;
}

#define ll long long
char s[maxn];
ll dp[maxn];
int main()
{
    while(~scanf("%s",s+))
    {
        sz=;
        root=newnode();
        last=root;
        ll p,q;
        scanf("%lld%lld",&p,&q);
        int n=strlen(s+);
        int j=;
        dp[]=p;
        extend(s[]-'a');
        state* cur=root->Next[s[]-'a'];
        for(int i=;i<=n;i++)
        {
            dp[i]=dp[i-]+p;
            while()
            {
                while(cur!=root && cur->link->len>=i-j-) cur=cur->link;
                if(cur->Next[s[i]-'a']!=NULL)
                {
                    cur=cur->Next[s[i]-'a'];
                    break;
                }
                else
                    extend(s[++j]-'a');
            }
            //cout<<i<<' '<<j<<endl;
            dp[i]=min(dp[i],dp[j]+q);
        }
        printf("%lld\n",dp[n]);
    }
}

 

PS:本人从来没搞明白subset,substring,section,子串,子序列,区间的区别,因此一般习惯称其为“连续子串/序列”,“非连续子串/子序列”

版权声明
本文为[Isakovsky]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/isakovsky/p/11246450.html