洛谷 P3041 视频游戏的连击Video Game Combos

难度一般，不过这个数位DP其实应该叫做记忆化搜索

题意：玩游戏时可以通过按键组合打出combo技能；然后是已知N个combo的按键方式，然后求K次按键最多可以放出的combo技能（combo技能之间可以重叠）。

思路：

  1. 在AC自动机上如果一个点表示一个字符串以及它的后缀，则一个点可以对应多个combo技能（这是关键点）
  2. 可以先用拓扑排序处理出每个点对应了多少个combo技能，处理时要用fail的反向边即refail计算入度
  3. 然后就是数位DP啦，这题没啥坑点，思路简洁

题目描述

Bessie is playing a video game! In the game, the three letters ‘A’, ‘B’, and ‘C’ are the only valid buttons. Bessie may press the buttons in any order she likes; however, there are only N distinct combos possible (1 <= N <= 20). Combo i is represented as a string S_i which has a length between 1 and 15 and contains only the letters ‘A’, ‘B’, and ‘C’.

Whenever Bessie presses a combination of letters that matches with a combo, she gets one point for the combo. Combos may overlap with each other or even finish at the same time! For example if N = 3 and the three possible combos are “ABA”, “CB”, and “ABACB”, and Bessie presses “ABACB”, she will end with 3 points. Bessie may score points for a single combo more than once.

Bessie of course wants to earn points as quickly as possible. If she presses exactly K buttons (1 <= K <= 1,000), what is the maximum number of points she can earn?

贝西在玩一款游戏，该游戏只有三个技能键 “A”“B”“C”可用，但这些键可用形成N种(1 <= N<= 20)特定的组合技。第i个组合技用一个长度为1到15的字符串S_i表示。

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

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

输入格式

  • Line 1: Two space-separated integers: N and K.

  • Lines 2…N+1: Line i+1 contains only the string S_i, representing combo i.

输出格式

  • Line 1: A single integer, the maximum number of points Bessie can obtain.

输入输出样例

输入
3 7
ABA
CB
ABACB
输出
4
说明/提示

The optimal sequence of buttons in this case is ABACBCB, which gives 4 points–1 from ABA, 1 from ABACB, and 2 from CB.

//#pragma comment(linker, "/STACK:102400000,102400000")
#include "bits/stdc++.h"
#define pb push_back
#define ls l,m,now<<1
#define rs m+1,r,now<<1|1
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 4e2+10;
const int mod = 1e4+7;
const double eps = 1e-9;

char s[maxn];
int N, K;
int trie[maxn][26], fail[maxn], cnt;
vector<int> refail[maxn];
int in[maxn], num[maxn];
int dp[1010][maxn];

void insert() {
    int len=strlen(s), p=0;
    for(int i=0; i<len; ++i) {
        int k=s[i]-'A';
        if(!trie[p][k]) trie[p][k]=++cnt;
        p=trie[p][k];
    }
    num[p]++;
}

void build() {
    queue<int> q;
    for(int i=0; i<26; ++i) if(trie[0][i]) q.push(trie[0][i]);
    while(q.size()) {
        int now=q.front(); q.pop();
        for(int i=0; i<26; ++i) {
            if(trie[now][i]) {
                fail[trie[now][i]]=trie[fail[now]][i];
                refail[trie[fail[now]][i]].pb(trie[now][i]);
                in[trie[now][i]]++;
                q.push(trie[now][i]);
            }
            else trie[now][i]=trie[fail[now]][i];
        }
    }
}

void Toposort() {
    queue<int> q;
    for(int i=0; i<=cnt; ++i) if(!in[i]) q.push(i);
    while(q.size()) {
        int now=q.front(); q.pop();
        for(int i=0; i<refail[now].size(); ++i) {
            int v=refail[now][i];
            num[v]+=num[now];
            if(--in[v]==0) q.push(v);
        }
    }
}

int dfs(int pos, int now) {
    if(pos>K) return 0;
    if(~dp[pos][now]) return dp[pos][now];
    int ans=0;
    for(int i=0; i<26; ++i)
        ans=max(ans,num[trie[now][i]]+dfs(pos+1,trie[now][i]));
    return dp[pos][now]=ans;
}

int main() {
    //ios::sync_with_stdio(false);
    N=read(), K=read();
    for(int i=0; i<N; ++i) scanf("%s", s), insert();
    build();
    Toposort();
    memset(dp,-1,sizeof(dp));
    printf("%d\n", dfs(1,0));
}