HDU6583:Typewriter（dp+后缀自动机）

题意：

给出\(p,q\)，现在要你生成一个字符串\(s\)。

你可以进行两种操作：一种是花费\(p\)的代价随意在后面添加一个字符，另一种是花费\(q\)的代价可以随意赋值前面的一个子串。

现在问最小代价是多少。

思路：

考虑\(dp\)，那么就有转移方程：\(dp[i]=min\{dp[i-1]+p,dp[j]+q\}\)，即直接对两种操作取min即可。

注意到该\(dp\)方程有一个性质：其值肯定为单调不降的。因为如果有\(dp[i-1]>dp[i]\)，那此时我们跟着复制过来肯定更好，不能复制就花\(p\)在后面增加，那值岂不是也变大了？

所以转移方程中的\(j\)应为最远的一个\(j\)。

之后思路如下：

考虑维护离当前\(i\)最远的一个\(j\)，使得\(s[1,\cdots,j-1]\)的子串中含有\(s[j,\cdots,i]\)。
注意到\(j\)是单调不减的，考虑用后缀自动机来维护这样一个位置。
当向\(i+1\)转移时，若目前后缀自动机中无法成功向\(s[i+1]\)转移，那么将第\(j\)个字符加入后缀自动机并且\(j++\)，直到成功转移。
注意我们始终要保证后缀自动机中的状态长度尽可能小，这样我们才能保证\(j\)尽可能远，详见\(withdraw\)操作。

挺好的一道题，需要透彻分析问题的性质。

代码如下：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 4e5 + 5;

int p, q;

char s[N];

struct SAM{

    struct node{

        int ch[26];

        int len, fa;

        node(){memset(ch, 0, sizeof(ch)), len = 0;}

    }dian[N];

    int last, tot, now;

    void init(int n) {

        last = tot = now = 1;

        for(int i = 1; i <= 2 * n; i++) {

            for(int j = 0; j < 26; j++) dian[i].ch[j] = 0;

            dian[i].len = 0;

        }

    }

    void add(int c) {

        int p = last;

        int np = last = ++tot;

        dian[np].len = dian[p].len + 1;

        for(; p && !dian[p].ch[c]; p = dian[p].fa) dian[p].ch[c] = np;

        if(!p) dian[np].fa = 1;

        else {

            int q = dian[p].ch[c];

            if(dian[q].len == dian[p].len + 1) dian[np].fa = q;

            else {

                int nq = ++tot; dian[nq] = dian[q];

                dian[nq].len = dian[p].len + 1;

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

                for(; p && dian[p].ch[c] == q; p = dian[p].fa) dian[p].ch[c] = nq;

            }

        }

    }

    void withdraw(int lens) {

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

        if(now == 0) now = 1;

    }

    void trans(int t, int lens) {

        now = dian[now].ch[t];

        withdraw(lens);

    }

    bool match(int t) {

        return dian[now].ch[t];

    }

}A;

ll dp[N];

int main() {

    ios::sync_with_stdio(false); cin.tie(0);

    while(cin >> s + 1) {

        int n = strlen(s + 1);

        cin >> p >> q;

        A.init(n);

        int l = 2, r = 1;

        A.add(s[1] - 'a'); dp[1] = p;

        for(int i = 2; i <= n; i++) {

            ++r; int tmp = s[i] - 'a';

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

            while((!A.match(tmp) || r - l + 1 > i / 2) && l <= r) {

                A.add(s[l++] - 'a');

                A.withdraw(r - l);

            }

            A.trans(tmp, r - l + 1);

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

        }

        cout << dp[n] << '\n';

    }

    return 0;

}

巴特西

HDU6583:Typewriter（dp+后缀自动机）

最新文章

热门文章