[2019杭电多校第一场][hdu6583]Typewriter（后缀自动机&&dp）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6583

大致题意是说可以花费p在字符串后添加一个任意字符，或者花费q在字符串后添加一个当前字符串的子串。问最少花费多少可以得到目标串。

一开始想到的dp，dp[i]为得到目标串的1-i的最小花费。

那么dp[i]=min{dp[i-1]+p,dp[j-1]+q}，s[j~i]应该为s[1~j-1]的子串。

我们可以知道dp数组是一个单调递增的数组，用反证法可以证明：dp[i]由dp[i-1]转移就不用说了，如果dp[i]是由dp[j]转移过来且dp[i-1]>dp[i]，那么dp[i-1]也可以由dp[j]转移过来，所以不合法。

因为dp数组是递增的，则dp[i]如果是由第二种方法转移过来，则j应该是最小的。所以求最小的j满足s[j~i]应该为s[1~j-1]的子串。

dp[i]的第二种转移位置，应该在是dp[i-1]的第二种转移位置j的基础上往后移。

所以用双指针的位置，一个代表i，一个代表j，每次在后缀自动机上添加第j个位置的字符，如果s[j~i]在后缀自动机上可以匹配，则转移，不然就把j往后移。

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<algorithm>

 #include<cstring>

 #include<string>

 #include<queue>

 using namespace std;

 typedef long long ll;

 const ll maxn = 2e5 + ;

 const ll inf = 1e18;

 struct SAM {

     int cnt, last, now;

     int len[maxn * ], ch[maxn * ][], fa[maxn * ];

     void clear() {

         for (int i = ; i <= cnt; i++) {

             len[i] = fa[i] = ;

             memset(ch[i], , sizeof(ch[i]));

         }

     }

     void insert(int x) {

         int np = ++cnt, p = last;

         len[np] = len[p] + , last = np;

         while (p && !ch[p][x])

             ch[p][x] = np, p = fa[p];

         if (!p)

             fa[np] = ;

         else {

             int q = ch[p][x];

             if (len[q] == len[p] + )

                 fa[np] = q;

             else {

                 int nq = ++cnt;

                 len[nq] = len[p] + ;

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

                 fa[nq] = fa[q];

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

                 while (p&&ch[p][x] == q)

                     ch[p][x] = nq, p = fa[p];

             }

         }

     }

     int Match(int x) {

         return ch[now][x];

     }

     void withdraw(int lens) {

         while (now&&len[fa[now]] >= lens)now = fa[now];

         if (now == )now = ;

     }

     void Tran(int x, int lens) {

         now = ch[now][x];

         if (now == )now = ;

         withdraw(lens);

     }

 }SA;

 ll dp[maxn];

 char s[maxn];

 int main() {

     while (~scanf("%s", s + )) {

         ll p, q, len;

         memset(dp, , sizeof(dp));

         scanf("%lld%lld", &p, &q);

         len = strlen(s + );

         SA.cnt = SA.last = SA.now = ;

         SA.insert(s[] - 'a');

         dp[] = p;

         int l = , r = ;

         for (int i = ; i <= len; i++) {

             r++;

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

             while ((!SA.Match(s[i] - 'a') || r - l +  > (i + ) / ) && l <= r) {

                 SA.insert(s[l++] - 'a');

                 SA.withdraw(r - l);

             }

             SA.Tran(s[i] - 'a', r - l + );

             if (l <= r)

                 dp[r] = min(dp[r], dp[l - ] + q);

         }

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

         SA.clear();

     }

 }

巴特西

[2019杭电多校第一场][hdu6583]Typewriter（后缀自动机&&dp）

最新文章

热门文章