P1026 [NOIP2001 提高组] 统计单词个数
题目描述
给出一个长度不超过 200200 的由小写英文字母组成的字母串(该字串以每行 2020 个字母的方式输入,且保证每行一定为 2020 个)。要求将此字母串分成 �k 份,且每份中包含的单词个数加起来总数最大。
每份中包含的单词可以部分重叠。当选用一个单词之后,其第一个字母不能再用。例如字符串 this 中可包含 this 和 is,选用 this 之后就不能包含 th。
单词在给出的一个不超过 66 个单词的字典中。
要求输出最大的个数。
输入格式
每组的第一行有两个正整数 �,�p,k。 �p 表示字串的行数,�k 表示分为 �k 个部分。
接下来的 �p 行,每行均有 2020 个字符。
再接下来有一个正整数 �s,表示字典中单词个数。 接下来的 �s 行,每行均有一个单词。
输出格式
11个整数,分别对应每组测试数据的相应结果。
输入输出样例
输入 #1复制
1 3 thisisabookyouareaoh 4 is a ok sab
输出 #1复制
7
说明/提示
【数据范围】
对于 100%100% 的数据,2≤�≤402≤k≤40,1≤�≤61≤s≤6。
【样例解释】 划分方案为 this / isabookyoua / reaoh
【题目来源】
NOIP 2001 提高组第三题
这题做了好久......两个动态规划,我谈谈我用C语言的做法。
①每读取一行可以用strcat把字符串连在一起
②从字符串A中搜索单词word可以用char *p=strstr(A,word);
返回NULL则找不到,顺带可以用p-A==0来判断单词是否从A[0]开始匹配。
③先预处理出w[i][j],表示从i到j的单词数。可以倒着推,w[i][j]=w[i+1][j];(如果存在从A[i]字母开始的单词,则w[i][j]=w[i+1][j]+1.出现同一字母开头的多个单词也还是加1就够了.)
④F[i][j]表示前i个字母分成j段得到的最大单词数,答案是F[len][k],可以初始化一下F[i][i]和F[i][1]. 方程F(i,j)=max{ F(r,j-1)+w(r+1,i) (r=j...i-1) }. 意思就是把1..r的字母先分成j-1段,剩下的r+1..i的字母分成另一段。
#include<stdio.h>
#include<string.h>
int p,k,s,len,w[205][205],F[205][45];
char A[205],temp[25],word[10][205];
void Input(void)
{int i;scanf("%d%d",&p,&k); len=20*p;while(getchar()!='\n');while(p--){gets(temp);strcat(&A[1],temp);}scanf("%d",&s);while(getchar()!='\n');for(i=1;i<=s;i++) gets(word[i]);
}
int have(int x,int end)//是否存在以字符A[x]开头的单词
{int i; for(i=1;i<=s;i++){char *p=strstr(&A[x],word[i]);if(p!=NULL && p-&A[x]==0 && strlen(word[i])<=end-x+1) return 1;}return 0;
}
void Init(void)
{int i,j;for(j=len;j>=1;j--) for(i=j;i>=1;i--)if(have(i,j)) w[i][j]=w[i+1][j]+1;else w[i][j]=w[i+1][j];
}
void DP(void)
{int i,j,r;for(i=1;i<=k;i++) F[i][i]=F[i-1][i-1]+w[i][i];for(i=1;i<=len;i++) F[i][1]=w[1][i];for(i=1;i<=len;i++)for(j=2;j<=k&&j<i;j++)for(r=j;r<i;r++)if(F[i][j]<F[r][j-1]+w[r+1][i])F[i][j]=F[r][j-1]+w[r+1][i];
}
int main(void)
{Input();Init();DP();printf("%d",F[len][k]);return 0;
}
相关文章:
P1026 [NOIP2001 提高组] 统计单词个数
题目描述 给出一个长度不超过 200200 的由小写英文字母组成的字母串(该字串以每行 2020 个字母的方式输入,且保证每行一定为 2020 个)。要求将此字母串分成 �k 份,且每份中包含的单词个数加起来总数最大。 每份中包含…...
CTFHub | eval执行
0x00 前言 CTFHub 专注网络安全、信息安全、白帽子技术的在线学习,实训平台。提供优质的赛事及学习服务,拥有完善的题目环境及配套 writeup ,降低 CTF 学习入门门槛,快速帮助选手成长,跟随主流比赛潮流。 0x01 题目描述…...
IP协议头
IP 4位版本号(version)4位头部长度(header length)8位服务类型(Type Of Service)16位总长度(total length)16位标识(id)3位标志字段13位分片偏移(…...
【xxl-job定时任务框架详解】
一,分布式任务调度 基本概念 分布式任务调度是一种用于在分布式环境中调度和执行任务的技术。在分布式系统中,由于存在多台服务器、多个进程和线程并行执行,因此需要一种机制来协调和管理任务的执行,避免任务冲突、重复执行、负载不均衡等问题。分布式任务调度通常由一个…...
7、在vscode上利用cmake构建多文件C++工程
文章目录 (1)创建如下工程文件夹:其中头文件放在include文件夹中,源文件放在src文件夹中(2)在vscode上打开工程文件夹,在对应的文件夹内建立相应的文件1)目录结构2)各文件…...
Linux操作系统网络模块
Linux操作系统的网络模块是负责网络通信的核心部分。它通过实现各种协议和算法,使得计算机能够在网络中进行数据交换和通信。网络模块主要包括以下几个方面的功能: (1)IP协议栈:负责处理网络层的数据包,实…...
不同批次板子采集到的传感器压力值不同
问题描述: M340B空压机主控板在接正常压力气源时,显示屏显示压力值过高并报警。 问题排查: 确认可能的故障点:压力传感器、硬件电路(供电电路、分压电路、ADC采样电路等)、单片机、软件; 排…...
设计模式--原型模式
目录 基本介绍 传统方式克隆 原型模式改进 浅拷贝和深拷贝 浅拷贝的介绍 深拷贝的介绍 原型模式的注意事项和细节 基本介绍 (1) 原型模式(prototype模式): 用原型实例指定创建对象的种类 并且通过拷贝这些原型 创建新的对象 (2) 原型模式是一种创建型设计模式 允许一个…...
C++智能指针shared_ptr详解
智能指针shared_ptr详解 一、简介二、底层原理2.1、引用计数2.2、shared_ptr的构造和析构2.3、shared_ptr的共享和拷贝2.4、循环引用问题 三、shared_ptr的使用3.1、创建一个shared_ptr3.2、共享一个shared_ptr3.3、使用删除器3.4、解除关联 四、使用示例总结 一、简介 C智能指…...
家政服务APP小程序开发功能详解
随着人们生活水平的提高,对家政服务的要求也越来越高。而传统的到家政公司寻找服务人员的方法显然已经无法满足人们需求,取而代之的是线上预约家政服务。家政服务App小程序软件可以满足用户在线预约,还可以根据自己的需求定制家政服务、选择家…...
【C++】deque的实现原理简单介绍
前言 deque被称为双端队列,它的出现主要是为了结合vector和list的优点并减小它们的缺点,实际上deque确实结合了vector和list的优点减小了它们的缺点,但是它的结合也让它自己的优点没有原始的vector和list那么极致,导致deque变得很…...
UWB隧道人员定位技术应用,施工作业安全精准保障
隧道施工的安全不仅关系到工程项目的质量和施工效率,也关系到我国的资金安全、施工人员和人民的生命财产安全。如何有效加强隧道施工的安全管理能力,成为隧道施工企业管理者最关心的问题。国家铁道局在《关于加强铁路隧道工程安全工作的若干意见》中指出…...
15.2 矩阵链乘法
1.代码 public class MatrixChainMultiplication {public static void main(String[] args) { // 在该代码中,我们首先创建了两个n * n的矩阵m和s,分别用于记录最优值和分割点。 其中m 矩阵 通过i j 来显示在i到j的矩阵链中最优解 // // …...
向隐形冠军学习:聚焦人效,用时间管理提效益
注: 本文来源于盖雅工场联合创始人兼CEO 章新波 在2023狮山论坛“ 向隐形冠军学习: 聚焦人效,用时间管理提效益 ”的主题分享。 文|章新波 整理 |盖雅学苑 在人力资源行业以及各大企业,「人效」这个词…...
Protocol Buffers Go Generated Code Guide
Protocol Buffers Go 代码生成指南 本主题准确描述了协议缓冲区编译器为任何给定的协议定义生成的Go代码。 编译器调用 协议缓冲区编译器需要一个插件来生成Go 代码。使用Go 1.16或更高版本安装,方法是运行: go install google.golang.org/protobuf/…...
Python VTK STL 映射三维模型表面距离
目录 前言: 效果: 实现步骤: Code: 前言: 本文介绍了Python VTK映射三维模型表面距离,通过如何使用VTK计算两个三维模型(stl)的表面距离,并将其距离值以颜色映射到模型,可用于对比 两相模型…...
C# 异常处理机制和常见的异常类型
在 C# 中,异常处理是一个非常重要的概念,它可以让我们在程序发生错误时进行有效的处理,使程序具备更好的鲁棒性。C# 异常处理机制基于 try-catch-finally 语句块,其基本用法如下: try {// 可能会抛出异常的代码 } cat…...
【0187】客户端身份验证配置文件视图之pg_hba_file_rules
文章目录 1. 客户端身份验证配置文件视图2. 视图效果相关阅读: 【0179】配置PostgreSQL以允许远程连接 【0180】PG内核通过pg_hba.conf完成客户端认证(1) 【0181】PG内核通过pg_hba.conf完成客户端认证(2)...
模糊层次分析法(FAHP)Python实现
文章目录 理论基础三角模糊数概念参考 Python源码测试 理论基础 \quad 模糊层次分析法( F A H P FAHP FAHP)将模糊理论( F u z z y S e t Fuzzy Set FuzzySet)嵌入到基本层次分析法( A H P AHP AHP)中。 A …...
gdb切换窗口焦点
为了辅助调试,一般会使用layout src,调起TUI显示代码: 然而这种情况下我们写命令很不方便,无法方便地使用上一条命令、退格等。 按动上下左右方向键盘只会移动代码框,然而在伪终端下,可以用鼠标滚轮来上下…...
eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)
说明: 想象一下,你正在用eNSP搭建一个虚拟的网络世界,里面有虚拟的路由器、交换机、电脑(PC)等等。这些设备都在你的电脑里面“运行”,它们之间可以互相通信,就像一个封闭的小王国。 但是&#…...
智慧医疗能源事业线深度画像分析(上)
引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...
多场景 OkHttpClient 管理器 - Android 网络通信解决方案
下面是一个完整的 Android 实现,展示如何创建和管理多个 OkHttpClient 实例,分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...
MMaDA: Multimodal Large Diffusion Language Models
CODE : https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA,它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构…...
el-switch文字内置
el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...
Neo4j 集群管理:原理、技术与最佳实践深度解析
Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...
TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案
一、TRS收益互换的本质与业务逻辑 (一)概念解析 TRS(Total Return Swap)收益互换是一种金融衍生工具,指交易双方约定在未来一定期限内,基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...
云原生玩法三问:构建自定义开发环境
云原生玩法三问:构建自定义开发环境 引言 临时运维一个古董项目,无文档,无环境,无交接人,俗称三无。 运行设备的环境老,本地环境版本高,ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...
NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合
在汽车智能化的汹涌浪潮中,车辆不再仅仅是传统的交通工具,而是逐步演变为高度智能的移动终端。这一转变的核心支撑,来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒(T-Box)方案:NXP S32K146 与…...
排序算法总结(C++)
目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指:同样大小的样本 **(同样大小的数据)**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...
