[luoguP2031] 脑力达人之分割字串（DP）

想了个4次方算法，没想到也A了，数据真是水。

其实两个字符串匹配那部分可以用kmp优化

——代码

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 int n, m, f[310];
 5 char s[310], a[501][310];
 6 
 7 inline int max(int x, int y)
 8 {
 9     return x > y ? x : y;
10 }
11 
12 int main()
13 {
14     int i, j, k, l, len;
15     scanf("%s %d", s + 1, &n);
16     for(i = 1; i <= n; i++) scanf("%s", a[i] + 1);
17     m = strlen(s + 1);
18     for(i = 1; i <= m; i++)
19         for(j = 1; j <= n; j++)
20         {
21             len = strlen(a[j] + 1);
22             if(i >= len)
23                 for(k = i; k; k--)
24                 {
25                     for(l = len; l; l--) if(s[k - (len - l)] ^ a[j][l]) break;
26                     if(!l) f[i] = max(f[i], f[k - len] + 1);
27                 }
28         }
29     printf("%d
", f[m]);
30     return 0;
31 }

View Code

正解

f[i] 表示前 i 个字符串的最优解

f[i] = max(f[i], f[i - 1])

f[i] = max(f[i], f[j - 1] + 1)　(len[j ~ i] 为字典中出现过的单词)

len[j ~ i] 是以 j 为前缀的单词，可以用trie树搞。

——代码

 1 #include <cstdio>
 2 #include <cstring>
 3 #define idx(x) x - 'a'
 4 #define max(x, y) ((x) > (y) ? (x) : (y))
 5 
 6 int n, cnt;
 7 int ch[150001][26], val[150001], f[301];
 8 char s[301], a[301];
 9 
10 inline void insert()
11 {
12     int i, x, now = 0, len = strlen(a);
13     for(i = 0; i < len; i++)
14     {
15         x = idx(a[i]);
16         if(!ch[now][x]) ch[now][x] = ++cnt;
17         now = ch[now][x];
18     }
19     val[now]++;
20 }
21 
22 int main()
23 {
24     int i, j, len, now;
25     scanf("%s", s + 1);
26     scanf("%d", &n);
27     for(i = 1; i <= n; i++)
28     {
29         scanf("%s", a);
30         insert();
31     }
32     len = strlen(s + 1);
33     for(i = 1; i <= len; i++)
34     {
35         f[i] = max(f[i], f[i - 1]);
36         for(j = i, now = 0; ch[now][idx(s[j])] && j <= len; j++)
37         {
38             now = ch[now][idx(s[j])];
39             if(val[now]) f[j] = max(f[j], f[i - 1] + 1);
40         }
41     }
42     printf("%d
", f[len]);
43     return 0;
44 }

View Code