string 基本操作:
substr(x,y) x是起始位置,y是长度;
返回的是这一段字符串;
先预处理sum[i][j],表示以i开头,最多的单词数;
从后往前寻找,保证开头没有被用过;
sum[i][j]=sum[i+1][j];
再找是否有新单词出现;
s.find()==0说明找到单词以开头开始;
然后dp,f[i][j]表示以i结尾分j段的最大单词数;
#include<cstdio>
#include<string>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std; string s,ch,a[];
int sum_dic,p,k; int sum[][]; bool check(int l,int r)
{
string x;
x=s.substr(l,r-l+);
for(int i=;i<=sum_dic;i++)
{
if(x.find(a[i])==) return ;
}
return ;
} int f[][]; int main()
{
scanf("%d%d",&p,&k);
s+="";
for(int i=;i<=p;i++)
{
cin>>ch;
s+=ch;
}
int len=s.length()-;
scanf("%d",&sum_dic);
for(int i=;i<=sum_dic;i++)
{
cin>>a[i];
} for(int i=len;i>=;i--)
{
for(int j=i;j>=;j--)
{
sum[j][i]=sum[j+][i];
if(check(j,i)) sum[j][i]++;
}
} f[][]=;
for(int i=;i<=k;i++) f[i][i]=f[i-][i-]+sum[i][i]; for(int i=;i<=len;i++) f[i][]=sum[][i]; for(int i=;i<=len;i++)
{
for(int j=;j<=k&&j<i;j++)
{
for(int l=j;l<i;l++)
{
f[i][j]=max(f[i][j],f[l][j-]+sum[l+][i]);
}
}
} printf("%d",f[len][k]); return ;
}
P1026 统计单词个数——substr的更多相关文章
-
luogu P1026 统计单词个数
题目链接 luogu P1026 统计单词个数 题解 贪心的预处理母本串从i到j的最大单词数 然后dp[i][j] 表示从前i个切了k次最优解 转移显然 代码 #include<cstdio&g ...
-
[luogu]P1026 统计单词个数[DP][字符串]
[luogu]P1026 统计单词个数 题目描述 给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入,且保证每行一定为20个).要求将此字母串分成k份(1&l ...
-
P1026 统计单词个数 区间dp
题目描述 给出一个长度不超过200200的由小写英文字母组成的字母串(约定;该字串以每行2020个字母的方式输入,且保证每行一定为2020个).要求将此字母串分成kk份(1<k \le 401& ...
-
P1026 统计单词个数 (动态规划)
题目描述 给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入,且保证每行一定为20个).要求将此字母串分成k份(1<k<=40),且每份中包含的单 ...
-
洛谷 P1026 统计单词个数 Label:dp
题目描述 给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入,且保证每行一定为20个).要求将此字母串分成k份(1<k<=40),且每份中包含的单 ...
-
洛谷 P1026 统计单词个数
题目描述 给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入,且保证每行一定为20个).要求将此字母串分成k份(1<k<=40),且每份中包含的单 ...
-
[NOIP2001] 提高组 洛谷P1026 统计单词个数
题目描述 给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入,且保 证每行一定为20个).要求将此字母串分成k份(1<k<=40),且每份中包含的 ...
-
【dp】P1026 统计单词个数
题目描述 给出一个长度不超过200200的由小写英文字母组成的字母串(约定;该字串以每行2020个字母的方式输入,且保证每行一定为2020个).要求将此字母串分成kk份(1<k \le 401& ...
-
洛谷P1026 统计单词个数【区间dp】
题目:https://www.luogu.org/problemnew/show/P1026 题意: 给定一个字符串,要求把他分成k段.给定s个单词,问划分成k段之后每段中包含的单词和最大是多少. 一 ...
随机推荐
-
SDK Manager 中 没有 Support Library怎么弄?
SDK Manager 中 没有 Support Library怎么弄?求大神帮忙 百度上面说的基本都试了,依旧没有弄出来 点击"Packages" > "Show ...
-
java.lang.ClassNotFoundException: org.apache.struts2.dispatcher.ng.filter.StrutsPrepareAndExecuteFilter
报这个错是因为加的struts的jar包有问题... 另外,jar包应该放在WEB-INF下的lib文件夹里面,且不必Add to build path,该目录下的jar包会自动引入 使用struts ...
-
The Network Adapter could not establish the connection解决办法
用 oracle net manager 将监听改为IP地址,将服务命名也改为IP地址,然后数据库连接改为IP地址方式不要用localhost
-
CoreData (四)备
监听NSFetchedResultsController 之前说过, NSFetchedResultsController是有两个重要的功能. 第一:NSFetchedResultsControlle ...
-
[转]Linux编译和安装boost库
1. 下载boost安装包并解压缩 到http://www.boost.org/下载boost的安装包,以boost_1_58_0.tar.gz为例 下载完成后进行解压缩: tar zxvf boos ...
-
Nginx系列一:正向代理和反向代理、Nginx工作原理、Nginx常用命令和升级、搭建Nginx负载均衡
转自https://www.cnblogs.com/leeSmall/p/9351343.html 仅供个人学习 一.什么是正向代理.什么是反向代理 1. 正向代理,意思是一个位于客户端和原始服务器( ...
-
12 Best Live Chat Software for Small Business Compared (2019) 最佳的wordpress在线聊天工具推荐插件 来帮你和潜在客户互动
12 Best Live Chat Software for Small Business Compared (2019) Did you know that more than 67% of ...
-
Java各厂对外的优质博客
1.美团:https://tech.meituan.com/ 2.极客学院:http://wiki.jikexueyuan.com/list/java/
-
Timer TimerTask schedule scheduleAtFixedRate
jdk 自带的 timer 框架是有缺陷的, 其功能简单,而且有时候它的api 不好理解. import java.util.Date; import java.util.Timer; import ...
-
风控3—iv算法详细解释
python信用评分卡(附代码,博主录制) https://study.163.com/course/introduction.htm?courseId=1005214003&utm_camp ...