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

题意：

有个打字机，在当前字符串后新加一个字花费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=;

#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，子串，子序列，区间的区别，因此一般习惯称其为“连续子串/序列”，“非连续子串/子序列”

巴特西

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

最新文章

热门文章