当前位置: 首页 > 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”…...

告别Transformer?手把手复现SegNeXt语义分割模型(附PyTorch代码)

从零实现SegNeXt&#xff1a;用纯卷积架构挑战Transformer的语义分割霸主地位 在计算机视觉领域&#xff0c;语义分割技术正经历着一场静默的革命。当大多数研究者将目光聚焦于Transformer架构时&#xff0c;SegNeXt却用纯粹的卷积神经网络&#xff08;CNN&#xff09;设计刷新…...

AntiDupl.NET:数字资产管理师的智能图片去重解决方案

AntiDupl.NET&#xff1a;数字资产管理师的智能图片去重解决方案 【免费下载链接】AntiDupl A program to search similar and defect pictures on the disk 项目地址: https://gitcode.com/gh_mirrors/an/AntiDupl 在当今视觉内容爆炸的时代&#xff0c;无论是专业摄影…...

Lumerical圆锥建模避坑指南:从参数计算到3D旋转生成的完整流程

Lumerical圆锥建模避坑指南&#xff1a;从参数计算到3D旋转生成的完整流程 在光学仿真领域&#xff0c;精确的几何建模往往是获得可靠结果的第一步。对于圆锥结构这种在光子晶体、超表面和纳米天线设计中广泛应用的形状&#xff0c;其建模过程看似简单却暗藏玄机。许多研究人员…...

SpringCloud Alibaba与Nacos版本不匹配?手把手教你解决‘Client not connected‘错误

SpringCloud Alibaba与Nacos版本兼容性实战&#xff1a;彻底解决Client not connected问题 微服务架构的复杂性往往隐藏在细节之中。当SpringCloud Alibaba项目启动时控制台突然抛出Client not connected, current status:STARTING的红色警告&#xff0c;不少开发者都会心头一紧…...

收藏!AI技能进化全解析:从聊天搭子到行业专家的成长之路

本文回顾了AI技能的演进过程&#xff0c;从最初只能进行简单对话的聊天机器人&#xff0c;到如今能够理解行业规范、执行复杂任务的智能体。文章详细介绍了AI技能发展的五个阶段&#xff1a;初级聊天机器人、通过函数调用实现工具交互、通用接口MCP规范、智能体引擎赋予环境感知…...

从乱码到清晰:一位开发者与iText7中文PDF的三年斗争史

从乱码到清晰&#xff1a;一位开发者与iText7中文PDF的三年斗争史 【免费下载链接】itext7-chinese-font 项目地址: https://gitcode.com/gh_mirrors/it/itext7-chinese-font "为什么我的PDF中文又变成方块了&#xff1f;" 这可能是每个Java开发者在处理中文P…...

【实战】Ubuntu20.04硬盘挂载与权限管理全攻略(从分区合并到ext4格式化)

1. 从Windows迁移到Ubuntu的硬盘处理痛点 刚接触Ubuntu的Windows用户经常会遇到一个头疼问题&#xff1a;原先在Windows下分好区的机械硬盘&#xff0c;在Ubuntu系统里居然"消失"了。这不是硬盘真的不见了&#xff0c;而是Linux系统对NTFS分区的识别机制不同。我去年…...

滑模控制消抖新思路:双曲正切函数VS饱和函数效果实测对比

滑模控制消抖技术深度对比&#xff1a;双曲正切函数与饱和函数的实战解析 在智能控制算法的演进历程中&#xff0c;滑模控制&#xff08;SMC&#xff09;因其强鲁棒性成为处理系统不确定性和外部干扰的利器。但传统符号函数带来的高频抖振问题&#xff0c;一直是工程师们亟待解…...

YOLOv5实战:如何用Inner-IoU提升小目标检测效果(附完整代码)

YOLOv5实战&#xff1a;用Inner-IoU解决小目标检测痛点的工程指南 无人机镜头下的蚂蚁、CT扫描中的微小结节、卫星图像里的车辆——当目标尺寸小于3232像素时&#xff0c;传统检测器的性能往往会断崖式下跌。我们团队在医疗影像分析项目中就曾遇到这样的困境&#xff1a;常规Io…...

2026Agent元年!手把手教你从0到1搭建高能智能体,小白也能秒变大神!

逼自己练完这些&#xff0c;你的Agent搭建就很牛了&#xff01;&#xff01;2026年可谓是Agent元年&#xff0c;智能体&#xff08;AI Agent&#xff09;正以惊人的速度重塑我们的工作方式&#xff0c;从简单的被动响应工具&#xff0c;进化为能自主规划、执行、协作的"数…...