题目传送门
sol:先通过AC自动机构建字典,用$dp[i]$表示长串前$i$位的最小代价,若有一个单词$s$是长串的前$i$项的后缀,那么可以用$dp[i - len(s)] + val(s)$转移到$dp[i]$。
- AC自动机
#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int, int> PII; const int MAXN = 500010; const LL INF = 0x3f3f3f3f3f3f3f3f; struct Trie { int son[MAXN][26], fail[MAXN], last[MAXN], dep[MAXN]; LL val[MAXN], dp[MAXN]; int tot, root; int add_node(int d) { memset(son[tot], -1, sizeof(son[tot])); dep[tot] = d; val[tot] = INF; return tot ++; } void init() { memset(dp, INF, sizeof(dp)); dp[0] = tot = 0; root = add_node(0); } void insert(char* s, LL v) { int p = root; for (int i = 0; s[i]; i++) { int index = s[i] - 'a'; if (son[p][index] == -1) son[p][index] = add_node(i + 1); p = son[p][index]; } val[p] = min(val[p], v); } void build() { queue<int> que; fail[root] = root; for (int i = 0; i < 26; i++) { if (son[root][i] == -1) son[root][i] = root; else { fail[son[root][i]] = root; last[son[root][i]] = root; que.push(son[root][i]); } } while (!que.empty()) { int p = que.front(); que.pop(); for (int i = 0; i < 26; i++) { if (son[p][i] == -1) son[p][i] = son[fail[p]][i]; else { fail[son[p][i]] = son[fail[p]][i]; if (val[son[fail[p]][i]] != INF) last[son[p][i]] = son[fail[p]][i]; else last[son[p][i]] = son[last[p]][i]; que.push(son[p][i]); } } } } LL slove(char* s) { int p = root, len = strlen(s); for (int i = 0; i < len; i++) { int index = s[i] - 'a'; p = son[p][index]; for (int tmp = p; tmp != root; tmp = last[tmp]) dp[i + 1] = min(dp[i + 1], dp[i + 1 - dep[tmp]] + val[tmp]); } if (dp[len] == INF) return -1; else return dp[len]; } } ac; char s[MAXN]; int main() { int n, v; scanf("%d", &n); ac.init(); for (int i = 1; i <= n; i++) { scanf("%s%d", s, &v); ac.insert(s, v); } ac.build(); scanf("%s", s); printf("%lld\n", ac.slove(s)); return 0; }
AC自动机不熟练,硬怼了三天才敲出来,一直超时。又学到了两个AC自动机的优化。