P3041 [USACO12JAN]Video Game G

P3041 [USACO12JAN]Video Game G

给定 $n$ 个字符串，求长度为 $m$ 的字符串能使 $n$ 个字符串出现次数和的最大值。

建 AC自动机，考虑 DP，$f _ {i , j}$ 表示在 AC自动机上 $i$ 点选择了 $j$ 个字符的最大价值。

可以得到转移方程：
$$
f _ {tr _ {i, j}, k + 1} = max\{f _ {i, k}\}
$$
注意转移顺序，其中 $i$ 在自动机上任意走动，没有顺序。需要先从小到大枚举 $k$ 。

查看代码

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int N = 1e4 + 10, M = 1e3 + 10, inf = 2e4;
char s[N];
int n, m, f[N][M];
int idx, cnt[N], nxt[N], tr[N][3];
void chkmax (int &x, int k)
{
    k > x && (x = k);
}
void build()
{
    queue <int> q;
    for (int i = 0; i < 3; i++)
        tr[0][i] && (q.push(tr[0][i]), 0);
    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        for (int i = 0; i < 3; i++)
        {
            int &p = tr[t][i];
            if (!p)
                p = tr[nxt[t]][i];
            else
            {
                nxt[p] = tr[nxt[t]][i];
                q.push(p);
            }
        }
        cnt[t] += cnt[nxt[t]];
    }
}
void insert (int len, char *str)
{
    int p = 0;
    for (int i = 1; i <= len; i++)
    {
        int &t = tr[p][str[i] - 'A'];
        !t && (t = ++idx);
        p = t;
    }
    cnt[p]++;
}
void dfs (int x)
{
    for (int i = 0; i < 3; i++)
    {
        if (!tr[x][i])
            continue;
        for (int j = 0; j < m; j++)
            chkmax(f[tr[x][i]][j + 1], f[x][j] + cnt[tr[x][i]]);
        dfs(tr[x][i]);
    }
}
int main ()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%s", s + 1);
        insert(strlen(s + 1), s);
    }
    build();
    for (int i = 1; i <= idx; i++)
        for (int j = 0; j <= m; j++)
            f[i][j] = -inf;
    for (int k = 0; k < m; k++)
        for (int i = 0; i <= idx; i++)
            for (int j = 0; j < 3; j++)
                chkmax(f[tr[i][j]][k + 1], f[i][k] + cnt[tr[i][j]]);
    int res = 0;
    for (int i = 0; i <= idx; i++)
        chkmax(res, f[i][m]);
    printf("%d", res);
    return 0;
}