laekov

本来想做点英语作业的。想10分钟把这题搞定的。结果傻了去写trie树dp又傻了没有考虑终点也可以有子结点。

我真是无药可救了。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int tcnt;

struct trie_node {

int d, e, t[26];

inline trie_node(int d0 = 0) {

e = 0;

d = d0 + 1;

memset(t, 0, sizeof(t));

}

inline int ins(char c) {

if (!t[c - 97])

t[c - 97] = ++ tcnt;

return t[c - 97];

}

inline int trans(char c) {

return t[c - 97];

}

};

const int inf = 0x3f3f3f3f;

const int maxs = 15009;

const int maxl = 309;

int n, l, trt, f[2][maxs];

char a[maxl], tmp[maxl];

trie_node tr[maxs];

void trieIns(char* a) {

int p = trt;

for (; *a; ++ a)

p = tr[p]. ins(*a);

tr[p]. e = 1;

}

int dp() {

int cur = 0, prv = 1;

memset(f, 0x3f, sizeof(f));

f[cur][trt] = 0;

for (int i = 0; i < l; ++ i) {

swap(cur, prv);

for (int j = 1; j <= tcnt; ++ j)

f[cur][j] = inf;

for (int j = 1; j <= tcnt; ++ j)

if (f[prv][j] < inf) {

f[cur][j] = min(f[cur][j], f[prv][j] + 1);

int tmp = tr[j]. trans(a[i]);

if (tmp) {

if (tr[tmp]. e)

f[cur][trt] = min(f[cur][trt], f[prv][j]);

f[cur][tmp] = min(f[cur][tmp], f[prv][j]);

}

}

}

return f[cur][trt];

}

int main() {

#ifndef ONLINE_JUDGE

freopen("in.txt", "r", stdin);

#endif

scanf("%d%d%s", &n, &l, a);

trt = 1;

tcnt = 1;

for (int i = 0; i < n; ++ i) {

scanf("%s", tmp);

trieIns(tmp);

}

printf("%d\n", dp());

}