洛谷P1026统计单词个数题解--zhengjun

Bena ·

更新时间:2024-09-21

· 725 次阅读

题目描述

给出一个长度不超过 200200200 的由小写英文字母组成的字母串（该字串以每行 202020 个字母的方式输入，且保证每行一定为 202020 个）。要求将此字母串分成 kkk 份，且每份中包含的单词个数加起来总数最大。

每份中包含的单词可以部分重叠。当选用一个单词之后，其第一个字母不能再用。例如字符串 this 中可包含 this 和 is，选用 this 之后就不能包含 th。

单词在给出的一个不超过 666 个单词的字典中。

要求输出最大的个数。

输入格式

每组的第一行有两个正整数 p,kp,kp,k。 ppp 表示字串的行数，kkk 表示分为 kkk 个部分。

接下来的 ppp 行，每行均有 202020 个字符。

再接下来有一个正整数 sss，表示字典中单词个数。接下来的 sss 行，每行均有一个单词。

输出格式

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

输入输出样例 输入 #1 复制

1 3
thisisabookyouareaoh
4
is
a
ok
sab

输出 #1 复制

说明/提示 【数据范围】

对于 100%100\%100% 的数据，2≤k≤402 \le k \le 402≤k≤40，1≤s≤61 \le s \le 61≤s≤6。

【样例解释】

划分方案为 this/isabookyoua/reaohthis / isabookyoua / reaohthis/isabookyoua/reaoh

思路

首先，这是一道有点难度的动态规划。
用 fi,jf_{i,j}fi,j 表示从尾巴用了 iii 个字符分了 jjj 段的最多有多少个单词。
则转移方程不难想到：
fi,j=max(fi,j,fl,j−1+suml+1,i)f_{i,j}=max(f_{i,j},f_{l,j-1}+sum_{l+1,i})fi,j=max(fi,j,fl,j−1+suml+1,i)
sumsumsum 就是从 jjj 到 iii 的单词个数
然后 sumsumsum 就可以在前面预处理暴力算出来

代码

#include
using namespace std;
int p,n,m,k,f[210][50],sum[210][210];
string s,a[10];
bool check(int l,int r){
    string x=s.substr(l,r-l+1);//这个函数就是返回字符串s从第l个字符开始后面的r-l+1个字符所组成的字符串
    for(int i=1;i>p>>k;
    for(int i=1;i>ch;
        s+=ch;
    }
    cin>>n;
	m=s.length()-1;
    for(int i=1;i>a[i];
    for(int i=m;i>=1;i--)
    	for(int j=i;j>=1;j--){
    	    sum[j][i]=sum[j+1][i];
   	        if(check(j,i))
			    sum[j][i]++;
   		}
    f[0][0]=0;
    for(int i=1;i<=k;i++)
		f[i][i]=f[i-1][i-1]+sum[i][i];
    for(int i=1;i<=m;i++)
		f[i][1]=sum[1][i];
    for(int i=1;i<=m;i++)
    	for(int j=1;j<=k&&j<i;j++)
    		for(int k=j;k<i;k++)
    			f[i][j]=max(f[i][j],f[k][j-1]+sum[k+1][i]);
    printf("%d",f[m][k]);
    return 0;
}

谢谢–zhengjun
作者：A_zjzj

p1 单词

1024 个赞