题目描述
给出一个长度不超过 200 的由小写英文字母组成的字母串（该字串以每行 20 个字母的方式输入，且保证每行一定为 20 个）。要求将此字母串分成 k 份，且每份中包含的单词个数加起来总数最大。
每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串 this 中可包含 this 和 is，选用 this 之后就不能包含 th。
单词在给出的一个不超过 6 个单词的字典中。
要求输出最大的个数。
输入格式
每组的第一行有两个正整数 p,k . p 表示字串的行数，k 表示分为 k 个部分。
接下来的 p 行，每行均有 20 个字符。
再接下来有一个正整数 s 表示字典中单词个数。 接下来的 s 行，每行均有一个单词。
输出格式
1 个整数，分别对应每组测试数据的相应结果。
输入输出样例
输入
1 3
thisisabookyouareaoh
4
is
a
ok
sab
输出
7
【样例解释】 划分方案为 this / isabookyoua / reaoh
-
此题第一个难点是意识到如果有两个字母同时符合要求, 最短的那个会更优(贪心).
-
第二个难点是字符串的预处理. End[x]表示从x开始的最短的那个单词的最后一个字母的位置.如abcde里找ab单词, 那么End[1]=2.
-
此题最难的部分是DP方程如何转移.
-
我们假设DP[i][q]表示已经到了第i个字符, 如果此时在第i位字符后面砍第q刀,会得到的单词出现次数的总和.
-
首先想到DP[i][q]从DP[j][q-1]来转移, 同时查找j+1到i位的单词个数. 但是 O(n3*k2), 会超.
-
那么只好优化这个转化过程. 我们可以发现j+2到i位的单词个数可以算到j+1到i位的单词个数里面. 所以j采取倒序循环, 用一个t累计,从i一直到q
(为啥是q, 你想啊, 你想砍第q刀是不是至少要从第q个字母开始枚举)
代码如下
#include<bits/stdc++.h>
#define MN 1005
#define Inf 0x3f3f3f3f
#define ll long long
using namespace std;
int p,k,s,len,End[MN];
ll dp[MN][45];
string str;
char Sen[MN];
char Wor[11][MN];
bool Find(int x,int y){
string Cmp="";
for(int i=x;i<=y;i++)Cmp+=Sen[i];
for(int i=1;i<=s;i++)
if(string(Cmp)==string(Wor[i]+1))
{
return 1;
}
return 0;
}
void pre(int i){
for(int j=i;j<=len;j++){
if(Find(i,j)){
End[i]=j;
return;
}
}
}
void Inp(){
memset(End,0x3f,sizeof(End));
cin>>p>>k;
len=p*20;
for(int i=1;i<=len;i++){
cin>>Sen[i];
}
cin>>s;
for(int i=1;i<=s;i++)
scanf("%s",Wor[i]+1);
}
int main(){
Inp();
for(int i=1;i<=len;i++)
pre(i);
for(int i=1;i<=len;i++){
for(int q=1;q<=k;q++){
int t=0;
for(int j=i;j>=q;j--){
if(End[j]<=i)
t++;
dp[i][q]=max(dp[i][q],dp[j-1][q-1]+t);
}
}
}
printf("%ld",dp[len][k]);
return 0;
}