dp，就是dp\bold d\bold pdp。
按本题的要求，我们首先要实现一个workworkwork函数，代表在目标的字符串中有多少个单词。我在这里用的是直接用二维数组推一遍，当做初始化提前把workworkwork函数执行了。
作者这里使用的是倒推。
我们想，每次插入一个字母，如果在当前位置上不能构成字母，那和不加这个字母有什么区别呢？如果在当前位置上能构成字母，也是在不插入这个字母的基础上单词量+1+1+1，于是，我们可以先设worki,jwork_{i,j}worki,j
为第iii位到第jjj位所包含的单词数，初始时把他赋值为worki+1,jwork_{i+1,j}worki+1,j ，再判断他可不可以构成单词，如果可以，worki,jwork_{i,j}worki,j 就+1+1+1。
核心代码
dp部分：
和 [NOIP2000 提高组] 乘积最大 很像，可以设fi,jf_{i,j}fi,j 为前iii个字符分成jjj段可以得到的最大单词数，再依次枚举第jjj段的起点进行状态转移，就可以了。
状态转移方程：
fij={work1,i j=1fi−1,j−1+workij i=jmaxj≤k≤i{fk−1,j−1+workk,i} 1≤i≤p×20,1≤j≤min(k,i)\begin{equation*} f_{ij}= \begin{cases} work_{1,i}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ j=1\\
f_{i-1,j-1}+work_ij\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i=j\\ \max_{j\leq k\leq i}\{f_{k-1,j-1}+work_{k,i}\}\ \ \ 1\leq i\leq p\times20,1\leq j\leq \min(k,i) \end{cases} \end{equation*} fij =⎩⎨⎧ work1,i j=1fi−1,j−1 +worki
j i=jmaxj≤k≤i {fk−1,j−1 +workk,i } 1≤i≤p×20,1≤j≤min(k,i)
> LaTeX\LaTeXLATE X好难打,跪求一个免费的赞
而最后的答案为fp×20,kf_{p\times 20,k}fp×20,k 。
第一条转移方程是当只分111份的时候，那肯定全选，所以字母量为work1,iwork_{1,i}work1,i 。
第二条转移方程是当份数和字母数相同，即每一份只有一个字母，所以直接从上一个状态fi−1,j−1f_{i-1,j-1}fi−1,j−1 加上当前的价值worki,jwork_{i,j}worki,j 就可以了。
第三条转移方程是枚举开头kkk，其他的也不用多说了。
注意事项：
> 1.由于workworkwork函数使用的是倒推，所以循环要从大到小。
> 2.一个字母只能对应一个单词的开头，所以一旦找到单词符合，直接break。
> 3.在第三条转移方程中, jjj循环的上限为min(k,i)\min(k,i)min(k,i)，是因为执行的过程中可能份数过多，字母不够分。
最后祝大家早日
拿下AC！！！
AC代码
