題目鏈接
手寫一下AC自動機(jī)（我可沒說我之前不是手寫的）
Trie上dp，每個點(diǎn)的貢獻(xiàn)加上所有是他后綴的串的貢獻(xiàn)，也就是這個點(diǎn)到根的fail鏈的和。
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXK = 1010;
const int MAXN = 1010;
struct ACA{int next[5], num, fail;
}AC[MAXN];
int f[MAXK][MAXN];
int n, k, cnt, ans;
char a[30];
queue <int> q;
void insert(){int len = strlen(a + 1), p = 0, w;for(int i = 1; i <= len; ++i){w = a[i] - 'A';if(!AC[p].next[w])AC[p].next[w] = ++cnt;p = AC[p].next[w];}++AC[p].num;
}
void build(){int now;for(int i = 0; i < 3; ++i)if(AC[0].next[i])q.push(AC[0].next[i]);while(q.size()){now = q.front(); q.pop();for(int i = 0; i < 3; ++i)if(AC[now].next[i]){AC[AC[now].next[i]].fail = AC[AC[now].fail].next[i];q.push(AC[now].next[i]);}else AC[now].next[i] = AC[AC[now].fail].next[i];AC[now].num += AC[AC[now].fail].num;}
}
void dp(){for(int i = 0; i <= k; ++i)for(int j = 1; j <= cnt; ++j)f[i][j] = -2147483647;for(int i = 1; i <= k; ++i)for(int j = 0; j <= cnt; ++j){for(int k = 0; k < 3; ++k)f[i][AC[j].next[k]] = max(f[i][AC[j].next[k]], f[i - 1][j] + AC[AC[j].next[k]].num);}for(int i = 1; i <= cnt; ++i)ans = max(ans, f[k][i]);
}
int main(){scanf("%d%d", &n, &k);for(int i = 1; i <= n; ++i){scanf("%s", a + 1);insert();}build();dp();printf("%d\n", ans);return 0;
}
轉(zhuǎn)載于:https://www.cnblogs.com/Qihoo360/p/10918586.html
總結(jié)
以上是生活随笔為你收集整理的【洛谷 P3041】 [USACO12JAN]视频游戏的连击Video Game Combos（AC自动机，dp）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
