【题解】洛谷 P1026，codevs1040 统计单词个数

我应该要滚粗了，这么一道水题目都交了 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 上交的代码，洛谷上的没有多组数据)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<algorithm>
using namespace std;
int po,k,n,T;
char ss[202],s[205];
int p[205],f[205][45];
int main()
{
    int i,j,t,len,ll;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d\n",&po,&k);
        memset(f,0,sizeof(f));
        memset(p,0,sizeof(p));
        strcpy(s,"");
        for(i=1;i<=po;i++){scanf("%s",ss);strcat(s,ss);}
        scanf("%d\n",&n);len=strlen(s);
        for(i=1;i<=n;i++){
            scanf("%s",ss);ll=strlen(ss);
            for(t=0;t<=len-ll;t++){
                int bj=0;
                for(j=0;j<ll;j++)
                    if(s[t+j]!=ss[j]){bj=1;break;}
                if(!bj)if(!p[t]||t+ll-1<p[t])p[t]=t+ll-1;
            }
        }
        for(i=0;i<len;i++)
            for(j=1;j<=min(k,i+1);j++){
                int tot=0;
                for(t=i;t>=j-1;t--){
                    if(p[t]<=i&&p[t])tot++;
                    if(t-1>=0)f[i][j]=max(f[i][j],f[t-1][j-1]+tot);
                    else f[i][j]=max(f[i][j],tot);
                }
        }
        printf("%d\n",f[len-1][k]);
    }
    return 0;
}