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 题意分析:从N张票据中选,且总价值不超过M的票据的最大价值(背包问题) K天限制 一、处理K天限制: 1.对于输入的是月 日的格式,很常用的方式是…...
【Android】Kotlin学习之Lambda表达式
java和kotlin对比 Lambda语法 Lambda隐形参数 it 也可以不使用指定的名称it, 可以 自定义 Lambda 使用下划线...
YOLOv5-7.0改进(四)添加EMA注意力机制
前言 关于网络中注意力机制的改进有很多种,本篇内容从EMA注意力机制开始! 往期回顾 YOLOv5-7.0改进(一)MobileNetv3替换主干网络 YOLOv5-7.0改进(二)BiFPN替换Neck网络 YOLOv5-7.0改进(三&…...
TCP协议的确认应答机制
TCP(Transmission Control Protocol)是一种面向连接的、可靠的、基于字节流的传输层协议,它在网络通信中扮演着至关重要的角色。其中,确认应答机制是TCP协议中的一个核心概念,它确保了数据的可靠传输。本文将详细介绍J…...
【论文阅读笔记】MAS-SAM: Segment Any Marine Animal with Aggregated Features
1.论文介绍 MAS-SAM: Segment Any Marine Animal with Aggregated Features MAS-SAM:利用聚合特征分割任何海洋动物 Paper Code(空的) 2.摘要 最近,分割任何模型(SAM)在生成高质量的对象掩模和实现零拍摄图像分割方面表现出卓越…...
C语言中的精确宽度类型
概述 在 C 语言标准库 <stdint.h> 中定义了一系列精确宽度的整数类型,这些类型保证了它们的位数宽度,从而允许编写跨平台的可移植代码。以下是一些常用的精确宽度整数类型: int8_t: 8位有符号整数uint8_t: 8位无符号整数int16_t: 16位…...
大数据比赛-环境搭建(一)
1、安装VMware Workstation 链接:https://pan.baidu.com/s/1IvSFzpnQFl3svWyCGRtEmg 提取码:ukpo 内有安装包及破解方式,安装教程。 2、下载Ubuntu系统 阿里巴巴开源镜像站-OPSX镜像站-阿里云开发者社区 (aliyun.com) 点击下载ÿ…...
微信小程序原生组件使用
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类别
数据集格式:Pascal VOC格式YOLO格式(不包含分割路径的txt文件,仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数):8375 标注数量(xml文件个数):8375 标注数量(txt文件个数):8375 标注…...
2024HW Linux应急响应基础学习
首先展示关于Linux的关键目录,这是应急响应查看的关键: 常用命令 top //查看进程资源的占用情况 ps -aux //查看进程 直接写ps aux也可以 netstat -antpl //查看网络连接 ls -alh /proc/pid //查看某个pid对应的可执行程序 pid记得修改 lsof /…...
烽火三十六技丨网络资产安全治理平台新版本发布,一文看懂四大核心优势
云计算、移动互联网、物联网等技术飞速发展,网络环境愈发开放互联,原有的资产管理方式已难以适应当下的变化。同时,网络资产需求的突发性和人为疏忽,也时常导致资产数量不明、类型模糊、安全漏洞检查不全面等问题。因此࿰…...
视频资源汇聚平台常见的几种接入方式
视频资源汇聚平台 视频汇聚平台可以实现海量资源的接入、汇聚、存储、处理、分析、运维等,平台具备轻量化接入能力,可支持多协议方式接入,包括主流标准协议GB28181、RTSP、ONVIF、RTMP、FLV、WEBSOCKET等,以及厂家私有协议与SDK接…...
LeetCode 212.单词搜索II
https://leetcode.cn/problems/word-search-ii/description/?envTypestudy-plan-v2&envIdtop-interview-150 文章目录 题目描述解题思路代码实现 题目描述 给定一个 m x n 二维字符网格 board 和一个单词(字符串)列表 words, 返回所有二…...
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代码+结果+可视化图)
大家好呀,从发布赛题一直到现在,总算完成了2024数维杯数学建模挑战赛生物质和煤共热解问题的研究完整的成品论文。 本论文可以保证原创,保证高质量。绝不是随便引用一大堆模型和代码复制粘贴进来完全没有应用糊弄人的垃圾半成品论文。 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绘图功能探索: 1、保持人物形象一致,适配更多的表情、动作 2、改变穿衣风格 3、小女孩的不同年龄段展示 4、不同社交平台的个性头像创作 如果不会写代码,可以问GPT。使用地址:我的GPT4 视频,B站会发&#…...
程序环境和预处理、编译链接过程、编译的几个阶段、运行环境、预定义符号等的介绍
文章目录 前言一、程序的翻译环境和执行环境二、编译链接过程三、编译的几个阶段四、运行环境五、预定义符号总结 前言 程序环境和预处理、编译链接过程、编译的几个阶段、运行环境、预定义符号的介绍。 一、程序的翻译环境和执行环境 在 ANSI C 的任何一种实现中,…...
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语言中的表示,前缀加0表示八进制数,前缀加0x表示十六进制数 基数数码名称描述代码和书本中的表示举例20 和 1二进制逢二进一,几乎所有的电子计算机内部都使用二进位制,分别为“0”…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
大数据学习栈记——Neo4j的安装与使用
本文介绍图数据库Neofj的安装与使用,操作系统:Ubuntu24.04,Neofj版本:2025.04.0。 Apt安装 Neofj可以进行官网安装:Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...
阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...
Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...
Cesium1.95中高性能加载1500个点
一、基本方式: 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...
循环冗余码校验CRC码 算法步骤+详细实例计算
通信过程:(白话解释) 我们将原始待发送的消息称为 M M M,依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)(意思就是 G ( x ) G(x) G(x) 是已知的)࿰…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...
[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?
论文网址:pdf 英文是纯手打的!论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误,若有发现欢迎评论指正!文章偏向于笔记,谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...
