HDU 6583 Typewriter 题解

——本题来自杭电多校第一场

题意：给定一个字符串，主角需要用打字机将字符串打出来，每次可以：

1.花费p来打出任意一个字符

2.花费q来将已经打出的某一段（子串）复制到后面去

对于这种最优化的问题，我们可以考虑dp

设置dp[i]表示已经打出前i个字符的最小花费，这样设状态是没有后效性的。

那么显然有：

　　　　　　　　　　　　dp[i] = dp[i-1] + p

这样就可以将第一种方案的转移算出来了

对于第二种方案，我们可以考虑维护一个j，使得 s[j+1……i] 是 s[1……j] 的子集（1），也就是说 s[j+1……i] 可以由 s[1……j] 中的一部分复制而来

具体实现利用后缀自动机来维护 s[1……j] 这个字符串，当不满足上述条件（1）时，就不断往后添加字符，并让 j = j + 1

当满足上述条件（1）时，就可以有：

　　　　　　　　　　　　dp[i] = min(dp[i], dp[j] + q)　

具体细节：当找到满足条件的j时，记录在后缀自动机上最后的匹配位置，每次i或者j变化的时候，检查cur的link指针指向位置的终点集合长度是否大于等于已匹配长度，如果是，就可以往link指针方向跳（对于这一部分不理解的话建议复习SAM的终点集合的性质），之后继续匹配。

代码：

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 const int maxn=;

 const int 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]);

     }

 }

注：由于本代码的sam用的是指针，HDU中G++编译器的指针为8字节，所以交G++的时候可能会因为常数太大而T，但是交C++可以600ms左右A掉

巴特西

HDU 6583 Typewriter 题解

最新文章

热门文章