视频游戏的连击 [USACO12JAN](AC自动机+动态规划)

默认大家都学过trie与AC自动机。

先求出fail，对于每个节点维护一个sum，sum[u]待表从根到u所形成的字符串能拿到几分。显然sum[u]=sum[fail] + (u是几个字符串的结尾)。

设dp[i][j]代表长度为i到trie树上的j号节点所得的最大分数，显然有dp[i+1][j的字符k儿子] = max{dp[i+1][j的字符k儿子], dp[i][j] + sum[j的字符k儿子]}

memset(dp, -, sizeof(dp));

dp[][] = ;

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

    for (int j = ; j <= tot; j++) {

        if (dp[i - ][j] == -) continue;

        for (int l = ; l < ; l++) {

            dp[i][trie[j][l]] = max(dp[i][trie[j][l]], dp[i - ][j] + sum[trie[j][l]]);

        }

    }

}

然后答案就是max{dp[k][i]}，i是所有trie树上的节点。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

using namespace std;

int n, k;

char s[];

int tu[][];

int trie[][], tot = ;

int fail[], sum[];

int dp[][];

queue<int> q;

int main() {

    scanf("%d%d", &n, &k);

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

        scanf("%s", s + );

        len = strlen(s + );

        int p = ;

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

            int m = s[j] - 'A';

            if (!trie[p][m]) trie[p][m] = ++tot;

            p = trie[p][m];

        }

        sum[p]++;

    }

    for (int i = ; i < ; i++) trie[][i] = ;

    fail[] = ;

    q.push();

    while (!q.empty()) {

        int p = q.front(); q.pop();

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

            if (trie[p][i]) {

                fail[trie[p][i]] = trie[fail[p]][i];

                sum[trie[p][i]] += sum[fail[trie[p][i]]];

                q.push(trie[p][i]);

            } else {

                trie[p][i] = trie[fail[p]][i];

            }

        }

    }

    memset(dp, -, sizeof(dp));

    dp[][] = ;

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

        for (int j = ; j <= tot; j++) {

            if (dp[i - ][j] == -) continue;

            for (int l = ; l < ; l++) {

                dp[i][trie[j][l]] = max(dp[i][trie[j][l]], dp[i - ][j] + sum[trie[j][l]]);

            }

        }

    }

    int ans = -;

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

        ans = max(ans, dp[k][i]);

    }

    cout << ans;

    return ;

}

巴特西

视频游戏的连击 [USACO12JAN](AC自动机+动态规划)

最新文章

热门文章