BZOJ_2580
可以先将字典树建出来并补成trie图，然后就可以用f[i][j]表示第i步走到第j个节点的时一共生成了多少个串，至于走到一个节点时会新增多少个串可以预处理出来，这样在trie图上进行dp即可。
#include#include #include #define MAXD 310#define MAXK 1010#define inf 0xc3c3c3c3int N, K, next[MAXD][3], num[MAXD], e, f[MAXK][MAXD], q[MAXD], P[MAXD];void add(int cur, int k){ memset(next[e], 0, sizeof(next[e])); num[e] = 0; next[cur][k] = e ++;}void init(){ char b[20]; memset(next[0], 0, sizeof(next[0])); num[0] = 0, e = 1; for(int i = 0; i < N; i ++) { scanf("%s", b); int cur = 0; for(int j = 0; b[j]; j ++) { int k = b[j] - 'A'; if(!next[cur][k]) add(cur, k); cur = next[cur][k]; } ++ num[cur]; } int rear = 0; q[rear ++] = 0; for(int i = 0; i < rear; i ++) { int x = q[i]; num[x] += num[P[x]]; for(int j = 0; j < 3; j ++) { if(next[x][j]) { q[rear ++] = next[x][j]; if(x == 0) P[next[x][j]] = 0; else P[next[x][j]] = next[P[x]][j]; } else next[x][j] = next[P[x]][j]; } }}void solve(){ memset(f, 0xc3, sizeof(f)); f[0][0] = 0; for(int i = 0; i < K; i ++) for(int j = 0; j < e; j ++) if(f[i][j] != inf) for(int k = 0; k < 3; k ++) { int x = next[j][k]; f[i + 1][x] = std::max(f[i + 1][x], f[i][j] + num[x]); } int ans = 0; for(int i = 0; i < e; i ++) ans = std::max(ans, f[K][i]); printf("%d\n", ans);}int main(){ while(scanf("%d%d", &N, &K) == 2) { init(); solve(); } return 0;}