[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 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

上一篇：[luoguP1103] 书本整理（DP）

下一篇：[luoguP2896] [USACO08FEB]一起吃饭Eating Together（DP）

---

DP trie树