传送门
想了个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 11 12 int main() 13 28 } 29 printf("%d\n", 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 19 val[now]++; 20 } 21 22 int main() 23 32 len = strlen(s + 1); 33 for(i = 1; i <= len; i++) 34 41 } 42 printf("%d\n", f[len]); 43 return 0; 44 }View Code
上一篇：[luoguP3252] [JLOI2012]树（DP）
下一篇：[luoguP2764] 最小路径覆盖问题（最大流 || 二分图最大匹配）
DP trie树
