我应该要滚粗了,这么一道水题目都交了3遍才A,发现是一个<=手误写成了<。我真的要滚粗了....
因为注意到一句这样神奇的话:每份中包含的单词可以部分重叠。当选用一个单词之后,其第一个字母不能再用。例如字符串this中可包含this和is,选用this之后就不能包含th之后,我们就很容易得到算法:
用一个p数组表示某个字符p位置开头是一个单词,结尾在哪里。很容易想到可以小小的贪个心,这个字母如果可以作为多个单词的开头的话,让结尾离它近一点的好。
然后我们用f[i][j]表示前i个字符划分成j段的最优答案,那么很容易得到状态转移方程:f[i][j]=max(f[k][j-1]+tot);(0<=k<i,tot表示的是从k+1到i的所有字符t,p[t]!=0且p[t]<=i的字符的个数。
那么我们就贴代码的说......(我贴的是codevs上交的代码,洛谷上的没有多组数据)