BZOJ 5325 [Jsoi2017]码农 题解

有一个很显然的 DP, 设 \(f[i]\) 表示前 \(i\) 考虑完了前 \(i\) 个字符的最小代价.

有两种转移:

• \(f[i]=f[i-1]+c[s_i]\).
• \(f[i]=min_{d_i-1\le j.

\(d_i\) 为最小的满足 (\([d_i,i]\) 是 \([1,d_{i}-1]\) 的子串) 的位置, 可以用 SAM 预处理出来.
具体来说, 将字符 \(s_i\) 依次加入, 维护一个指针表示当前最大的 \(p\) 使得 \([i+1,p]\) 是 \([1,i]\) 的子串.

然后发现第 2 种转移可以用单调队列优化, 就完了. 复杂度为 \(O(N)\).

#include 
#define N 202200
using namespace std;
int sze, las, lnk[N << 1], len[N << 1], nxt[N << 1][10];
 
void extend(int c) {
    int cur = ++sze, p; cur[len] = las[len] + 1;
    for (p = las; p && !nxt[p][c]; p = lnk[p])
        nxt[p][c] = cur;
    if (!p) lnk[cur] = 1;
    else {
        int q = nxt[p][c];
        if (len[q] == len[p] + 1) lnk[cur] = q;
        else {
            int cln = ++sze; cln[len] = p[len] + 1;
            memcpy(nxt[cln], nxt[q], sizeof nxt[q]);
            lnk[cln] = lnk[q], lnk[q] = lnk[cur] = cln;
            for (; p && nxt[p][c] == q; p = lnk[p])
                nxt[p][c] = cln;
        }
    } las = cur;
}
 
int n, a, b, c[12], d[N];
long long f[N];
char s[N];
 
inline int go(int p, int ch, int le) {
    while (p != 1 && !nxt[p][ch])
        p = lnk[p], le = len[p];
    if (nxt[p][ch]) p = nxt[p][ch], ++le;
    return le;
}
 
int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    for (int i = 0; i <= 9; ++i)
        scanf("%d", c + i);
    cin >> a >> b;
 
    las = sze = 1;
    int p = 1, t = 0, le = 0;
    for (int i = 1, j = 1; i <= n; ++i) {
        extend(s[i] - '0');
        while (t < n && go(p, s[t + 1] - '0', le) >= t + 1 - i) {
            int ch = s[++t] - '0';
            while (p != 1 && !nxt[p][ch])
                le = len[p = lnk[p]];
            if (nxt[p][ch]) p = nxt[p][ch], ++le;
        }
        while (j <= t) d[j++] = i + 1;
    }
 
    static int q[N], ql = 1, qr = 0;
    for (int i = 1; i <= n; ++i) {
        f[i] = f[i - 1] + c[s[i] - '0'];
        while (ql <= qr && q[ql] < d[i] - 1) ++ql;
        if (ql <= qr) {
            int j = q[ql];
            f[i] = min(f[i], f[j] + 1ll * a * (i - j) + b);
        }
        while (ql <= qr && (f[i] - 1ll * a * i) <= (f[q[qr]] - 1ll * a * q[qr])) --qr;
        q[++qr] = i;
    }
 
    cout << f[n] << endl;
 
    return 0;
}