HDU - 6583 Typewriter (后缀自动机+dp)

题意:你要打印一段字符串，往尾部添加一个字符需要花费p元，复制一段字符到尾部需要花费q元，求打印完全部字符的最小花费。

一开始想的贪心，后来发现忘了考虑p<q的情况了，还纳闷怎么不对..(囧)

设$dp[i]$为打印完前i个字符的最小花费

第一种转移是$dp[i+1]=min(dp[i+1],dp[i]+p)$，可以直接转移

第二种转移是$dp[j]=min(dp[j],dp[i]+q)$，对于每个i需要找到最大的j，使得$s[i+1,j]$是$s[1,i]$的子串。说到子串，就自然能想到后缀自动机。我们可以在i右移的同时扩展当前的后缀自动机，然后让j也右移，直到不能转移为止。如果对于每个i都让j从i开始往后走的话复杂度是$O(n^2)$的，会T掉，因此需要改进一下。有一个很巧妙的做法，用尺取的方法，每当i右移的时候，不必让j再从i开始走一遍，而是直接右移，如果不能转移的话，就尝试往父结点走，直到有转移为止，注意mxl(结点子串最大长度)不得小于j-i，否则无法完全覆盖$s[i+1,j]$区间。这样复杂度就是$O(n)$了。

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int N=4e5+,M=;

 char s[N];

 int n,fa[N],go[N][M],mxl[N],last,tot,p,q;

 ll dp[N];

 int newnode(int l) {int u=++tot; mxl[u]=l,memset(go[u],,sizeof go[u]); return u;}

 void add(int ch) {

     int p=last,np=last=newnode(mxl[p]+);

     for(; p&&!go[p][ch]; p=fa[p])go[p][ch]=np;

     if(!p)fa[np]=;

     else {

         int q=go[p][ch];

         if(mxl[q]==mxl[p]+)fa[np]=q;

         else {

             int nq=newnode(mxl[p]+);

             memcpy(go[nq],go[q],sizeof go[q]);

             fa[nq]=fa[q],fa[q]=fa[np]=nq;

             for(; p&&go[p][ch]==q; p=fa[p])go[p][ch]=nq;

         }

     }

 }

 int main() {

     while(scanf("%s%d%d",s,&p,&q)==) {

         n=strlen(s),tot=;

         last=newnode();

         memset(dp,0x3f,sizeof dp),dp[]=;

         for(int i=,j=,u=; i<n; add(s[i]-'a'),++i) {

             for(; j<n; u=go[u][s[j]-'a'],++j) {

                 for(; !go[u][s[j]-'a']&&fa[u]&&mxl[fa[u]]>=j-i; u=fa[u]);

                 if(!go[u][s[j]-'a'])break;

             }

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

         }

         printf("%lld\n",dp[n]);

     }

     return ;

 }

后记：我又尝试了使用后缀数组+线段树的方法，复杂度$O(nlogn)$，然而这题时限卡得太死了过不去，QAQ

巴特西

HDU - 6583 Typewriter (后缀自动机+dp)

最新文章

热门文章