Video Game Combos [USACO2012]

时间：2022-04-17 20:37:20

【题目描述】
贝西在玩一款游戏，该游戏只有三个技能键 (texttt{A,B,C}) 可用，但这些键可用形成N种((1 le Nle 20))特定的组合技。第(i)个组合技用一个长度为(1)到(15)的字符串(S_i)表示。

当贝西输入的一个字符序列和一个组合技匹配的时候，他将获得(1)分。特殊的，他输入的一个字符序列有可能同时和若干个组合技匹配，比如(N=3)时，3种组合技分别为"(texttt{ABA})", "(texttt{CB})", 和"(texttt{ABACB})",若贝西输入"(texttt{ABACB})"，他将获得(3)分。

若贝西输入恰好(K) ((1 le K le 1000))个字符，他最多能获得多少分？

【输入格式】
第一行包含两个整数(N)和(K)

接下来(N 1)行，第(i 1)行包含字符串(S_i)

【输出格式】
输出最大获得多少分。

题解

发现是要你构造一个长串去匹配若干给出的串 所以自然想到AC自动机

设(operatorname{f}(x))为 x到根的fail链上的 打了结束标记的点个数。

假设把那个长串给你了 那匹配套路无非就是在AC自动机上跳 每跳到一个点x 分数就加上(operatorname{f}(x))。(如果不懂请去学刁一下AC自动机)

那反正这(N)个串是不会变了 所以建好AC自动机之后把每个点x的(operatorname{f}(x))预处理出来

然后显然是个DP 设 (dp[i][j]) 表示 枚举到答案串的第(i)位，最后一位在AC自动机的(j)号节点上

转移方程就是枚举(i,j) 枚举(kin [0,25])表示枚举到的字母 (dp[i 1][j] = max(dp[i 1][son[j][k]], dp[i][j] f(son[j][k])))

不需要特判什么(son[j][k]=0)之类的 答案串一直在节点0打转也是无所谓的 不影响DP

影响DP的是 有些状态(dp[i][j])是无法到达的 所以我们先把整个dp数组设为(-1) 然后让(dp[0][0]=0) 如果枚举到(i,j dp[i][j]=-1)那就表示这个状态无法到达 要跳过

#include <bits/stdc  .h>
using namespace std;

int n, m; 
char s[30];
int ch[10005][30], fail[10005], val[10005], tot;
int dp[1005][1005];
bool tag[100005];

inline void insert(char *str, int l) {
    int x = 0;
    for (int i = 1; i <= l; i  ) {
        if (!ch[x][str[i] - 'A']) {
            ch[x][str[i] - 'A'] =   tot;
        }
        x = ch[x][str[i] - 'A'];
    }
    tag[x] = 1;
}

queue<int> q;

inline void getfail() {
    for (int i = 0; i < 26; i  ) if (ch[0][i]) q.push(ch[0][i]);
    while (!q.empty()) {
        int x = q.front(); q.pop();
        for (int i = 0; i < 26; i  ) {
            if (ch[x][i]) fail[ch[x][i]] = ch[fail[x]][i], q.push(ch[x][i]);
            else ch[x][i] = ch[fail[x]][i];
        }
    }
}

inline void calc() {
    for (int i = 0; i <= tot; i  ) {
        for (int j = i; j; j = fail[j]) {
            if (tag[j]) val[i]  ;
        }
    }
}

inline void DP() {
    memset(dp, -1, sizeof(dp));
    dp[0][0] = 0;
    for (int i = 0; i < m; i  ) {
        for (int j = 0; j <= tot; j  ) {
            if (dp[i][j] == -1) continue;
            for (int k = 0; k < 26; k  ) {
                dp[i 1][ch[j][k]] = max(dp[i 1][ch[j][k]], dp[i][j]   val[ch[j][k]]);
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i  ) {
        scanf("%s", s 1);
        insert(s, strlen(s 1));
    }
    getfail(); 
    calc();
    DP();
    int ans = 0;
    for (int i = 0; i <= tot; i  ) {
        ans = max(ans, dp[m][i]);
    }
    printf("%dn", ans);
    return 0;
}

相关文章