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”…...
Leetcode 3576. Transform Array to All Equal Elements
Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接:3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到…...
DAY 47
三、通道注意力 3.1 通道注意力的定义 # 新增:通道注意力模块(SE模块) class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...
涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战
“🤖手搓TuyaAI语音指令 😍秒变表情包大师,让萌系Otto机器人🔥玩出智能新花样!开整!” 🤖 Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制(TuyaAI…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...
Linux离线(zip方式)安装docker
目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1:修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本:CentOS 7 64位 内核版本:3.10.0 相关命令: uname -rcat /etc/os-rele…...
RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)
RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发,后来由Pivotal Software Inc.(现为VMware子公司)接管。RabbitMQ 是一个开源的消息代理和队列服务器,用 Erlang 语言编写。广泛应用于各种分布…...
RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill
视觉语言模型(Vision-Language Models, VLMs),为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展,机器人仍难以胜任复杂的长时程任务(如家具装配),主要受限于人…...
GraphQL 实战篇:Apollo Client 配置与缓存
GraphQL 实战篇:Apollo Client 配置与缓存 上一篇:GraphQL 入门篇:基础查询语法 依旧和上一篇的笔记一样,主实操,没啥过多的细节讲解,代码具体在: https://github.com/GoldenaArcher/graphql…...
从零手写Java版本的LSM Tree (一):LSM Tree 概述
🔥 推荐一个高质量的Java LSM Tree开源项目! https://github.com/brianxiadong/java-lsm-tree java-lsm-tree 是一个从零实现的Log-Structured Merge Tree,专为高并发写入场景设计。 核心亮点: ⚡ 极致性能:写入速度超…...
StarRocks 全面向量化执行引擎深度解析
StarRocks 全面向量化执行引擎深度解析 StarRocks 的向量化执行引擎是其高性能的核心设计,相比传统行式处理引擎(如MySQL),性能可提升 5-10倍。以下是分层拆解: 1. 向量化 vs 传统行式处理 维度行式处理向量化处理数…...
