题目描述

给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入，且保证每行一定为20个)。要求将此字母串分成k份( 1 < k ≤ 40 )，且每份中包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串this中可包含this和is，选用this之后就不能包含th)。
单词在给出的一个不超过6个单词的字典中。
要求输出最大的个数。

输入描述:

每组的第一行有2个正整数(p,k)
p表示字串的行数,k表示分为k个部分。
接下来的p行，每行均有20个字符。
再接下来有1个正整数s，表示字典中单词个数。(1 ≤ s ≤ 6 )
接下来的s行，每行均有1个单词。

输出描述:

1个整数，分别对应每组测试数据的相应结果。

示例1

输入
1 3
thisisabookyouareaoh
4
is
a
ok
sab
输出
7

解答

由于题目数据范围很很很小，所以可以有各种奇奇怪怪的方法可以水过去。
这里介绍两种比较适用（准确）的方法（正解）：
1.DP 考虑一个表示前i个字母分成了j段时最大的单词数目，那么我们枚举一个位置p，在这个位置将字符串分成两段，那么这个，我们定义表示在文本串（即文章）的第i个位置到第j个位置，以每个位置开头，以j为结尾，总共有多少单词。那么s数组可以用(单词)的效率预处理，然后dp数组可以用的效率直接搞出来。
DP的优化手段：如果单词数目比较多弄个Trie就可以把number的常数直接弄掉。同时s数组应该还可以用递推搞一搞，那么又可以把预处理的效率弄成。然后在实际操作中dp数组还可以用单调队列优化一下，那么就可以把一个length(T)给弄掉。
那么总效率就是
但是数据是非常小的，所以没必要这么麻烦。
2.贪心。我们考虑一下对分段为什么可以贪心。显然，如果我们将一个字符串分成了两段，那么对于每段的单词数是相互独立的，不会相互影响，符合无后效性。然后对于每次分段，实际上我们是把前面一段可以延伸到后面的单词数直接给减掉了，那么我们其实就可以把每次分段时每个位置被删掉会产生的负面贡献算出来，取个最小的，减掉，重复搞一搞，直到分成k段。这个我没打，具体可以参考楼下dalao们的。毕竟DP大法才是正道（手动滑稽）

参考代码（加了个Trie，所以代码长了点）： 
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=201;
int f[N][51],s[N][N],val[N*N],ch[N*N][26];
int NodeCnt=0,n,k,m,len;
string T,in;
void insert(string in){
    int u=0;
    for (int i=0;i<in.length();i++){
        int c=in[i]-'a';
        if (!ch[u][c])ch[u][c]=++NodeCnt;
        u=ch[u][c];
    }
    val[u]=1;
}
int query(int st,int en){
    int tot=0;
    for (int i=st;i<=en;i++){
        int u=0;
        for (int j=i;j<=en;j++){
            int c=T[j]-'a';
            if (!ch[u][c])break;
            u=ch[u][c];
            if (val[u]){tot++;break;}
        }
    }
    return tot;
}
int main(){
    ios::sync_with_stdio(false);
    while (cin>>n>>k){
        T="";
        for (int i=0;i<n;i++){
            cin>>in;
            T=T+in;
        }
        len=T.length();
        cin>>m; 
        for (int i=0;i<m;i++){
            cin>>in;
            insert(in);
        }
        for (int i=0;i<len;i++)
            for (int j=i;j<len;j++)
                s[i][j]=query(i,j);
        memset(f,~0x3f,sizeof(f));
        for (int i=0;i<len;i++)
            f[i][1]=s[0][i];
        for (int i=0;i<len;i++)
            for (int j=2;j<=k;j++)
                for (int p=0;p<i;p++)
                    f[i][j]=max(f[i][j],f[p][j-1]+s[p+1][i]);
        cout<<f[len-1][k];
    }
    return 0;
}
顺便提一句，此题数据非常水，我一开始把dp方程的写错了，同时把s数组只开到50，竟然过了4个点（一共才5个）！所以.....


来源：I_AM_HelloWord