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] << '
';
    }
    return 0;
}

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

相关推荐