【洛谷1026】【NOIP2001】统计单词个数
统计 个数 洛谷 单词
2023-09-11 14:14:41 时间
题面
题目描述
给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入,且保证每行一定为20个)。要求将此字母串分成k份(1<k<=40),且每份中包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。当选用一个单词之后,其第一个字母不能再用。例如字符串this中可包含this和is,选用this之后就不能包含th)。
单词在给出的一个不超过6个单词的字典中。
要求输出最大的个数。
输入格式:
每组的第一行有二个正整数(p,k)
p表示字串的行数;
k表示分为k个部分。
接下来的p行,每行均有20个字符。
再接下来有一个正整数s,表示字典中单词个数。(1<=s<=6)
接下来的s行,每行均有一个单词。
输出格式:
一个整数,分别对应每组测试数据的相应结果。
输入输出样例
输入样例#1:
1 3
thisisabookyouareaoh
4
is
a
ok
sab
输出样例#1:
7
说明
this/isabookyoua/reaoh
题解
这是一道很容(keng)易(die)的DP题
我表示什么也不想说
f[i][j]表示前i个字符分成j份的最大单词数
那么,我们不难退出递推关系式
f[i][j]=max{f[k][j-1]+w[k+1][j]}(k< i)
其中w[i][j]表示i到j的单词数
现在的问题就是如何求出w的值
方法很多
直接暴力就可以了
注意!暴力请不要使用substr截出子串再来判断,否则会超时
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
//f[i][j]表示前i个字母分成j段能够得到的最大单词个数
//f[i][j]=max{f[k][j-1]+num[k+1][i]}
//num[i][j]表示i到j的单词个数
string ss;
string s;
int f[210][210],w[210][210];
int num[210][210];
bool vis[210];
string a[20];
int b[210];
int n,p,k,l;
inline bool cmp(string a,string b)
{
return a.length()<b.length();
}
int Count(string ss)
{
int tot=0;
int ll=ss.length();
bool fl=false;
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;++i)//枚举字典
{
for(int j=0;j<=ll-b[i];++j)//枚举字符串
if(!vis[j])
{
fl=false;
for(int k=0;k<b[i];++k)
if(a[i][k]!=ss[k+j])
{
fl=true;
break;
}
if(!fl)
{
++tot;
vis[j]=true;
}
}
}
return tot;
}
int main()
{
cin>>p>>k;
for(int i=1;i<=p;++i)
{
cin>>ss;
s=s+ss;
}
cin>>n;
l=s.length();
for(int i=1;i<=n;++i)
cin>>a[i];
sort(&a[1],&a[n+1],cmp);
for(int i=1;i<=n;++i)
b[i]=a[i].length();
for(int i=0;i<l;++i)
{
ss="";
for(int j=i;j<l;++j)
{
ss+=s[j];
w[i][j]=Count(ss);
}
}
for(int i=0;i<l;++i)
f[i][1]=w[0][i];
//cout<<"K="<<k<<endl;
for(int i=0;i<l;++i)
for(int j=2;j<=min(i+1,k);++j)
for(int z=j-1;z<i;++z)
f[i][j]=max(f[z][j-1]+w[z+1][i],f[i][j]);
cout<<f[l-1][k]<<endl;
return 0;
}
相关文章
- 从终端获取一个字符串,分别统计当中大写字母、小写字母、数字及其他字符的个数。
- Django訪问量和页面PV数统计
- Mysql-SQL优化-统计某种类型的个数
- 输入一行字符,分别统计出其中英文字母、空格、数字和其它字符的个数
- Python统计txt文档每行以指定字符结尾的个数
- 《机器学习与数据科学(基于R的统计学习方法)》——2.9 从网站中抓取数据
- 力扣解法汇总2180. 统计各位数字之和为偶数的整数个数
- 性能优化——统计信息——SQLServer自动更新和自动创建统计信息选项
- EXCEL-COUNTIF()统计符合区间上的值个数
- 【华为OD机试真题 java、python、c++】统计匹配的二元组个数(100%通过+复盘思路)
- MongoDB 的 MapReduce 大数据统计统计挖掘
- mysql按月查询统计(统计近12个月的项目个数)
- 华为OD机试 -统计匹配的二元组个数(JavaScript) | 机试题+算法思路+考点+代码解析 【2023】
- [Java]对字符串中的每一个单词个数进行统计
- odoo 单表数据统计,按天统计
- 【MySQL】count统计哪种更快
- openstack资源统计监控系列之ceilometer+gnocchi获取VM虚拟机网卡数据流量统计项目实战及实现源码(四)
- 习题5.10 编程统计用户从键盘输入的字符串中所包含的字母、数字和其它字符的个数。
- 【uoj#209】[UER #6]票数统计 组合数+乱搞
- python实现字符类型统计