当前位置: 首页 > news >正文

P8803 [蓝桥杯 2022 国 B] 费用报销

P8803 [蓝桥杯 2022 国 B] 费用报销

分析

最值问题——DP

题意分析:从N张票据中选,且总价值不超过M的票据的最大价值(背包问题) + K天限制

一、处理K天限制:

1.对于输入的是月 + 日的格式,很常用的方式是将每个月的天数打表,便于比较

2.对于第 i 张票据可选,那么选的上一张即第 i - 1张票据的日期应该在第 i 张的前K天

具体做法:将每张票据给出的日期转换为在这一年中的天数,准备一个前缀和数组s[],记录第一个月到第i个月的天数,日期(m,d)= s[m] + d

二、本题具体解法:

1.背包问题的分析:准备一个数组f[i][j](从前 i 个物品中选,且总价值不超过 j 的最大价值),任一f[i][j]都有选或不选两种选择(不选:f[i][j] = f[i-1][j]),选的话,f[i][j]只能从与其时间间隔大于K天的票据中选,所以:

2.对天数进行排序,准备一个数组op[](保存距离第 i 张票据最近且间隔天数大于K天的票据编号),在DP中作为不选的方程来源(f[i][j] = f[op[i]][j-v]+v)

代码 

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;const int N = 1010,M = 5010;
struct tickets{int m,d,v,t;
}p[N];
int op[N],n,m,k,s[13],f[N][M];
//打表
int day[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};//按天数排序
bool cmp(tickets a,tickets b)
{return a.t < b.t;
}int main()
{//月份前缀和for(int i = 2;i < 13;i ++) s[i] = s[i - 1] + day[i - 1];scanf("%d %d %d",&n,&m,&k);for(int i = 1;i <= n;i ++){int m,d,v;scanf("%d %d %d",&m,&d,&v);p[i].m = m;p[i].d = d;p[i].v = v;p[i].t = s[m] + d;}//对天数排序sort(p + 1,p + n + 1,cmp);//找到与i间隔大于等于K天且距离最近的点for(int i = 1;i <= n;i ++){for(int j = 0;j < i;j ++){if(p[i].t - p[j].t >= k) op[i] = j;}}//DP(背包问题模板)for(int i = 1;i <= n;i ++){for(int j = m;j >= p[i].v;j --){//f[i][j] = f[i - 1][j]; 滚动数组优化f[i][j] = max(f[i-1][j],f[op[i]][j-p[i].v] + p[i].v);}}printf("%d",f[n][m]);return 0;
}

相关文章:

P8803 [蓝桥杯 2022 国 B] 费用报销

P8803 [蓝桥杯 2022 国 B] 费用报销 分析 最值问题——DP 题意分析&#xff1a;从N张票据中选&#xff0c;且总价值不超过M的票据的最大价值&#xff08;背包问题&#xff09; K天限制 一、处理K天限制&#xff1a; 1.对于输入的是月 日的格式&#xff0c;很常用的方式是…...

【Android】Kotlin学习之Lambda表达式

java和kotlin对比 Lambda语法 Lambda隐形参数 it 也可以不使用指定的名称it, 可以 自定义 Lambda 使用下划线...

YOLOv5-7.0改进(四)添加EMA注意力机制

前言 关于网络中注意力机制的改进有很多种&#xff0c;本篇内容从EMA注意力机制开始&#xff01; 往期回顾 YOLOv5-7.0改进&#xff08;一&#xff09;MobileNetv3替换主干网络 YOLOv5-7.0改进&#xff08;二&#xff09;BiFPN替换Neck网络 YOLOv5-7.0改进&#xff08;三&…...

TCP协议的确认应答机制

TCP&#xff08;Transmission Control Protocol&#xff09;是一种面向连接的、可靠的、基于字节流的传输层协议&#xff0c;它在网络通信中扮演着至关重要的角色。其中&#xff0c;确认应答机制是TCP协议中的一个核心概念&#xff0c;它确保了数据的可靠传输。本文将详细介绍J…...

【论文阅读笔记】MAS-SAM: Segment Any Marine Animal with Aggregated Features

1.论文介绍 MAS-SAM: Segment Any Marine Animal with Aggregated Features MAS-SAM&#xff1a;利用聚合特征分割任何海洋动物 Paper Code(空的) 2.摘要 最近&#xff0c;分割任何模型&#xff08;SAM&#xff09;在生成高质量的对象掩模和实现零拍摄图像分割方面表现出卓越…...

C语言中的精确宽度类型

概述 在 C 语言标准库 <stdint.h> 中定义了一系列精确宽度的整数类型&#xff0c;这些类型保证了它们的位数宽度&#xff0c;从而允许编写跨平台的可移植代码。以下是一些常用的精确宽度整数类型&#xff1a; int8_t: 8位有符号整数uint8_t: 8位无符号整数int16_t: 16位…...

大数据比赛-环境搭建(一)

1、安装VMware Workstation 链接&#xff1a;https://pan.baidu.com/s/1IvSFzpnQFl3svWyCGRtEmg 提取码&#xff1a;ukpo 内有安装包及破解方式&#xff0c;安装教程。 2、下载Ubuntu系统 阿里巴巴开源镜像站-OPSX镜像站-阿里云开发者社区 (aliyun.com) 点击下载&#xff…...

微信小程序原生组件使用

1、video组件使用 <view class"live-video"><video id"myVideo" src"{{videoSrc}}" bindplay"onPlay" bindfullscreenchange"fullScreenChange" controls object- fit"contain"> </video&g…...

[数据集][目标检测]纸箱子检测数据集VOC+YOLO格式8375张1类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;8375 标注数量(xml文件个数)&#xff1a;8375 标注数量(txt文件个数)&#xff1a;8375 标注…...

2024HW Linux应急响应基础学习

首先展示关于Linux的关键目录&#xff0c;这是应急响应查看的关键&#xff1a; 常用命令 top //查看进程资源的占用情况 ps -aux //查看进程 直接写ps aux也可以 netstat -antpl //查看网络连接 ls -alh /proc/pid //查看某个pid对应的可执行程序 pid记得修改 lsof /…...

烽火三十六技丨网络资产安全治理平台新版本发布,一文看懂四大核心优势

云计算、移动互联网、物联网等技术飞速发展&#xff0c;网络环境愈发开放互联&#xff0c;原有的资产管理方式已难以适应当下的变化。同时&#xff0c;网络资产需求的突发性和人为疏忽&#xff0c;也时常导致资产数量不明、类型模糊、安全漏洞检查不全面等问题。因此&#xff0…...

视频资源汇聚平台常见的几种接入方式

视频资源汇聚平台 视频汇聚平台可以实现海量资源的接入、汇聚、存储、处理、分析、运维等&#xff0c;平台具备轻量化接入能力&#xff0c;可支持多协议方式接入&#xff0c;包括主流标准协议GB28181、RTSP、ONVIF、RTMP、FLV、WEBSOCKET等&#xff0c;以及厂家私有协议与SDK接…...

LeetCode 212.单词搜索II

https://leetcode.cn/problems/word-search-ii/description/?envTypestudy-plan-v2&envIdtop-interview-150 文章目录 题目描述解题思路代码实现 题目描述 给定一个 m x n 二维字符网格 board 和一个单词&#xff08;字符串&#xff09;列表 words&#xff0c; 返回所有二…...

android 蓝牙技术 学习记录

一 。蓝牙介绍 蓝牙可以分为 经典蓝牙-----》传统蓝牙(BT 1.0/2.0/2.1)和高速蓝牙(BT3.0) 低功耗蓝牙 ----》BLE(BLE 4.0/4.1/4.2/5.0./5.1/5.2)和 Bluetooth Mesh 关于蓝牙协议。除开Mesh大致可以分为3层: App:上层协议有很多,例如ANP,HOGP,FTMP 等等 host:中…...

2024数维杯数学建模B题完整论文讲解(含每一问python代码+结果+可视化图)

大家好呀&#xff0c;从发布赛题一直到现在&#xff0c;总算完成了2024数维杯数学建模挑战赛生物质和煤共热解问题的研究完整的成品论文。 本论文可以保证原创&#xff0c;保证高质量。绝不是随便引用一大堆模型和代码复制粘贴进来完全没有应用糊弄人的垃圾半成品论文。 B题论…...

二叉树进阶 --- 中

目录 1. find 的递归实现 2. insert 的递归实现 3. erase 的递归实现 3.1. 被删除的节点右孩子为空 3.2. 被删除的节点左孩子为空 3.3. 被删除的节点左右孩子都不为空 4. 析构函数的实现 5. copy constructor的实现 6. 赋值运算符重载 7. 搜索二叉树的完整实现 1. fi…...

ChatGPT DALL-E绘图,制作各种表情包,实现穿衣风格的自由切换

DALL-E绘图功能探索&#xff1a; 1、保持人物形象一致&#xff0c;适配更多的表情、动作 2、改变穿衣风格 3、小女孩的不同年龄段展示 4、不同社交平台的个性头像创作 如果不会写代码&#xff0c;可以问GPT。使用地址&#xff1a;我的GPT4 视频&#xff0c;B站会发&#…...

程序环境和预处理、编译链接过程、编译的几个阶段、运行环境、预定义符号等的介绍

文章目录 前言一、程序的翻译环境和执行环境二、编译链接过程三、编译的几个阶段四、运行环境五、预定义符号总结 前言 程序环境和预处理、编译链接过程、编译的几个阶段、运行环境、预定义符号的介绍。 一、程序的翻译环境和执行环境 在 ANSI C 的任何一种实现中&#xff0c…...

MySQL导入导出详细教程

导出 语法 mysqldump [OPTIONS] database [tables] mysqldump [OPTIONS] --databases [OPTIONS] DB1 [DB2 DB3...] mysqldump [OPTIONS] --all-databases [OPTIONS]导出所有数据库 mysqldump -uroot -proot --all-databases >/tmp/all.sql导出db1、db2两个数据库的所有数…...

STM32F103学习笔记 | 8. 二,八,十,十六进制表示方式

文章目录 进制基本信息参考文献 进制基本信息 C语言中的表示&#xff0c;前缀加0表示八进制数&#xff0c;前缀加0x表示十六进制数 基数数码名称描述代码和书本中的表示举例20 和 1二进制逢二进一&#xff0c;几乎所有的电子计算机内部都使用二进位制&#xff0c;分别为“0”…...

OpenProject全球化协作本地化策略指南:打破语言壁垒的实战方案

OpenProject全球化协作本地化策略指南&#xff1a;打破语言壁垒的实战方案 【免费下载链接】openproject OpenProject is the leading open source project management software. 项目地址: https://gitcode.com/GitHub_Trending/op/openproject OpenProject作为领先的开…...

Cadence Virtuoso IC618版图验证全流程:解决PEX提参map error的详细步骤

Cadence Virtuoso IC618版图验证全流程&#xff1a;解决PEX提参map error的详细步骤 从IC514迁移到IC618的过程就像给老房子换新地基——表面上看功能相似&#xff0c;但底层架构的升级带来了全新的操作逻辑和隐藏的"陷阱"。最近三个月&#xff0c;我团队完成了7个项…...

【Mojo+Python混合部署失效真相】:92%开发者忽略的编译期符号冲突、运行时上下文隔离与调试断点丢失问题

第一章&#xff1a;MojoPython混合部署失效真相全景概览Mojo 作为新兴的高性能系统编程语言&#xff0c;设计初衷是与 Python 生态无缝互操作&#xff1b;然而在真实生产部署中&#xff0c;“Mojo Python 混合部署”常出现静默失败、ABI 不兼容、运行时崩溃或性能断崖式下降等…...

重磅:中科院分区退出历史!| 附2026年《新锐期刊分区表》完整版EXCEL.

3月24日&#xff0c;2026版《新锐期刊分区表》正式发布&#xff0c;随后引起了广泛的关注和争议。议论最多的&#xff0c;竟然是《新锐期刊分区表》到底是不是“中科院分区表”&#xff1f;3 月 25 日&#xff0c;公众号“新锐学术”发布《“走进新锐分区”专题&#xff1a;即将…...

SEO_避开这些常见误区,让你的SEO效果翻倍

<h2>避开这些常见误区&#xff0c;让你的SEO效果翻倍</h2> <p>在当今的互联网时代&#xff0c;搜索引擎优化&#xff08;SEO&#xff09;已经成为了每个网站和博客运营者必须掌握的技能之一。许多人在进行SEO时却会犯一些常见的错误&#xff0c;这些错误不仅…...

从VGG到ResNet:为什么说‘残差块’是深度学习模型‘卷’层数的救命稻草?

从VGG到ResNet&#xff1a;残差连接如何重塑深度神经网络的设计哲学 2014年ImageNet竞赛上&#xff0c;VGGNet凭借其规整的3x3卷积堆叠结构一举夺魁&#xff0c;将图像识别准确率提升到新高度。正当整个计算机视觉领域沉浸在"更深就一定更好"的乐观情绪中时&#xff…...

爱毕业aibye精选6大AI论文平台榜单:助力高效写作与智能降重,科研工作者的得力助手!

工具名称 核心功能 特色优势 Aibiye 论文生成降AI率 全学科覆盖、仿写优化、自动图表生成 Aicheck AI检测文献综述辅助 精准查新、3分钟高效成文 GPT学术版 润色/翻译/代码解释 多模型协同、PDF深度解析 摆平论文 大纲生成降重改写 三步出稿、本硕博通用 QuillB…...

Comsol 中微环谐振腔的环形波导耦合:波束包络与波动光学模块对比

Comsol微环谐振腔&#xff0c;环形波导耦和。 对比波束包络和波动光学两个不同模块。在光学领域&#xff0c;微环谐振腔因其独特的光学特性在众多应用中发挥着关键作用&#xff0c;比如光滤波、光传感等。而 Comsol 作为一款强大的多物理场仿真软件&#xff0c;为我们深入研究微…...

Qwen3.5小尺寸模型开源,9B碾压GPT开源版,消费级显卡就能跑

AI圈又出大新闻了✨ 阿里通义千问3.5系列小尺寸模型正式亮相&#xff0c;直接打破“小模型能力弱”的固有认知&#xff0c;甚至实现了“以小胜大”的逆袭&#xff0c;本地部署门槛直接拉到平民级&#xff01; 先上核心干货——这次千问3.5一口气推出了4款小尺寸模型&#xff0c…...

AutoDock Vina特殊金属元素对接技术指南:从问题诊断到方案落地

AutoDock Vina特殊金属元素对接技术指南&#xff1a;从问题诊断到方案落地 【免费下载链接】AutoDock-Vina AutoDock Vina 项目地址: https://gitcode.com/gh_mirrors/au/AutoDock-Vina 问题溯源&#xff1a;金属元素对接的技术瓶颈 在分子对接实践中&#xff0c;科研人…...