P1026 统计单词个数——substr

时间:2023-01-14 16:38:01

P1026 统计单词个数

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的更多相关文章

  1. luogu P1026 统计单词个数

    题目链接 luogu P1026 统计单词个数 题解 贪心的预处理母本串从i到j的最大单词数 然后dp[i][j] 表示从前i个切了k次最优解 转移显然 代码 #include<cstdio&g ...

  2. &lbrack;luogu&rsqb;P1026 统计单词个数&lbrack;DP&rsqb;&lbrack;字符串&rsqb;

    [luogu]P1026 统计单词个数 题目描述 给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入,且保证每行一定为20个).要求将此字母串分成k份(1&l ...

  3. P1026 统计单词个数 区间dp

    题目描述 给出一个长度不超过200200的由小写英文字母组成的字母串(约定;该字串以每行2020个字母的方式输入,且保证每行一定为2020个).要求将此字母串分成kk份(1<k \le 401& ...

  4. P1026 统计单词个数 &lpar;动态规划&rpar;

    题目描述 给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入,且保证每行一定为20个).要求将此字母串分成k份(1<k<=40),且每份中包含的单 ...

  5. 洛谷 P1026 统计单词个数 Label:dp

    题目描述 给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入,且保证每行一定为20个).要求将此字母串分成k份(1<k<=40),且每份中包含的单 ...

  6. 洛谷 P1026 统计单词个数

    题目描述 给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入,且保证每行一定为20个).要求将此字母串分成k份(1<k<=40),且每份中包含的单 ...

  7. &lbrack;NOIP2001&rsqb; 提高组 洛谷P1026 统计单词个数

    题目描述 给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入,且保 证每行一定为20个).要求将此字母串分成k份(1<k<=40),且每份中包含的 ...

  8. 【dp】P1026 统计单词个数

    题目描述 给出一个长度不超过200200的由小写英文字母组成的字母串(约定;该字串以每行2020个字母的方式输入,且保证每行一定为2020个).要求将此字母串分成kk份(1<k \le 401& ...

  9. 洛谷P1026 统计单词个数【区间dp】

    题目:https://www.luogu.org/problemnew/show/P1026 题意: 给定一个字符串,要求把他分成k段.给定s个单词,问划分成k段之后每段中包含的单词和最大是多少. 一 ...

随机推荐

  1. SDK Manager 中 没有 Support Library怎么弄?

    SDK Manager 中 没有 Support Library怎么弄?求大神帮忙 百度上面说的基本都试了,依旧没有弄出来 点击"Packages" > "Show ...

  2. java&period;lang&period;ClassNotFoundException&colon; org&period;apache&period;struts2&period;dispatcher&period;ng&period;filter&period;StrutsPrepareAndExecuteFilter

    报这个错是因为加的struts的jar包有问题... 另外,jar包应该放在WEB-INF下的lib文件夹里面,且不必Add to build path,该目录下的jar包会自动引入 使用struts ...

  3. The Network Adapter could not establish the connection解决办法

    用 oracle net manager 将监听改为IP地址,将服务命名也改为IP地址,然后数据库连接改为IP地址方式不要用localhost

  4. CoreData &lpar;四&rpar;备

    监听NSFetchedResultsController 之前说过, NSFetchedResultsController是有两个重要的功能. 第一:NSFetchedResultsControlle ...

  5. &lbrack;转&rsqb;Linux编译和安装boost库

    1. 下载boost安装包并解压缩 到http://www.boost.org/下载boost的安装包,以boost_1_58_0.tar.gz为例 下载完成后进行解压缩: tar zxvf boos ...

  6. Nginx系列一:正向代理和反向代理、Nginx工作原理、Nginx常用命令和升级、搭建Nginx负载均衡

    转自https://www.cnblogs.com/leeSmall/p/9351343.html 仅供个人学习 一.什么是正向代理.什么是反向代理 1. 正向代理,意思是一个位于客户端和原始服务器( ...

  7. 12 Best Live Chat Software for Small Business Compared &lpar;2019&rpar; 最佳的wordpress在线聊天工具推荐插件 来帮你和潜在客户互动

    12 Best Live Chat Software for Small Business Compared (2019)     Did you know that more than 67% of ...

  8. Java各厂对外的优质博客

    1.美团:https://tech.meituan.com/ 2.极客学院:http://wiki.jikexueyuan.com/list/java/

  9. Timer TimerTask schedule scheduleAtFixedRate

    jdk 自带的 timer 框架是有缺陷的, 其功能简单,而且有时候它的api 不好理解. import java.util.Date; import java.util.Timer; import ...

  10. 风控3—iv算法详细解释

    python信用评分卡(附代码,博主录制) https://study.163.com/course/introduction.htm?courseId=1005214003&utm_camp ...