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

蓝桥杯每日真题 - 第19天

题目:(费用报销)

题目描述(13届 C&C++ B组F题)

 

解题思路:

1. 问题抽象

本问题可以看作一个限制条件较多的优化问题,核心是如何在金额和时间约束下选择最优方案

  • 动态规划是理想的解决方法。

  • 我们定义 dp[i]到第 i 天为止的最大报销金额

2. 日期统一化

为了方便处理时间差,需将日期(月份和天数)统一转化为一年中的第几天。例如:

  • 1 月 1 日为第 1 天;

  • 2 月 1 日为第 32 天(31+1)。

这一步能让日期差的计算简单且高效。

3. 动态规划状态转移

  • 状态表示dp[i] 表示到第 i 天为止的最大报销金额。

  • 转移方程:对每张票据:

    • 如果报销当前票据:dp[i] = max(dp[i-1], dp[pre] + v[i]),其中 pre = i - K

    • 如果不报销当前票据:dp[i] = dp[i-1]

4. 优化思路

  • 按票据日期排序,确保动态规划时的时间顺序正确。

  • 动态更新 dp 数组,逐步累积最大金额。

代码实现(C语言):

#include <stdio.h>
#include <stdlib.h>typedef struct {int day, v;
} dps;int N, M, K;
int m[1009], d[1009];
dps dp[1009];
int a[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int p[366] = {0};// 计算每月对应的天数累计和
int month(int mi) {int sum = 0;for (int i = 0; i < mi - 1; i++) sum += a[i];return sum;
}// 将日期统一成一年中的第几天
void becomeday() {for (int i = 0; i < N; i++) {dp[i].day = month(m[i]) + d[i];p[dp[i].day] = dp[i].v;}
}// 比较函数,用于qsort排序
int cmp(const void *a1, const void *a2) {dps s1 = *(dps *)a1;dps s2 = *(dps *)a2;return s1.day - s2.day;
}int main() {scanf("%d%d%d", &N, &M, &K);for (int i = 0; i < N; i++) {scanf("%d%d%d", &m[i], &d[i], &dp[i].v);}// 转换日期并排序becomeday();qsort(dp, N, sizeof(dp[0]), cmp);// 动态规划for (int i = 1; i < 366; i++) {int pre = i - K >= 0 ? i - K : 0;if (p[i] + p[pre] <= M) {p[i] = p[i] + p[pre] > p[i - 1] ? p[i] + p[pre] : p[i - 1];} else {p[i] = p[i - 1];}}printf("%d", p[365]);return 0;
}

得到运行结果:

难度分析

⭐️⭐️⭐️⭐️⭐️难难难难难难

总结

本题核心在于将日期处理动态规划相结合,解决了多条件限制下的最优选择问题。
以下是总结要点:

  1. 日期统一化:通过天数累计简化日期差值计算。

  2. 动态规划核心:记录每一天的最大报销金额,并逐步更新。

  3. 代码结构清晰:日期处理、排序和动态规划分模块实现,方便理解和维护。

相关文章:

蓝桥杯每日真题 - 第19天

题目&#xff1a;&#xff08;费用报销&#xff09; 题目描述&#xff08;13届 C&C B组F题&#xff09; 解题思路&#xff1a; 1. 问题抽象 本问题可以看作一个限制条件较多的优化问题&#xff0c;核心是如何在金额和时间约束下选择最优方案&#xff1a; 动态规划是理想…...

CentOS7.9.2009的yum更换vault地窖保险库过期源,epel的archive归档源 笔记241117

CentOS7.9.2009的yum更换vault地窖保险库过期源,epel的archive归档源 笔记241117 备份 /etc/yum.repos.d 文件夹 tempUri/etc/yum.repos.d ; sudo cp -a $tempUri $tempUri.$(date %0y%0m%0d%0H%0M%0Sns%0N).bak清空 /etc/yum.repos.d 文件夹 sudo rm -rf /etc…...

Spark SQL大数据分析快速上手-完全分布模式安装

【图书介绍】《Spark SQL大数据分析快速上手》-CSDN博客 《Spark SQL大数据分析快速上手》【摘要 书评 试读】- 京东图书 大数据与数据分析_夏天又到了的博客-CSDN博客 Hadoop完全分布式环境搭建步骤-CSDN博客,前置环境安装参看此博文 完全分布模式也叫集群模式。将Spark目…...

Java面试题2024-Java基础

Java基础 1、 Java语言有哪些特点 1、简单易学、有丰富的类库 2、面向对象&#xff08;Java最重要的特性&#xff0c;让程序耦合度更低&#xff0c;内聚性更高&#xff09; 3、与平台无关性&#xff08;JVM是Java跨平台使用的根本&#xff09; 4、可靠安全 5、支持多线程 2、…...

局域网协同办公软件,2024安全的协同办公软件推荐

在2024年&#xff0c;随着数字化转型的深入和远程工作需求的增加&#xff0c;协同办公软件已成为企业提升工作效率、优化沟通流程的重要工具。 以下是一些值得推荐的安全的协同办公软件&#xff1a; 钉钉 功能全面&#xff1a;钉钉是一款综合性极强的企业级协同软件&#xff…...

osg、osgearth简介及学习环境准备

一、osg简介&#xff08;三维场景图渲染与调度引擎&#xff09; OSG是Open Scene Graphic 的缩写&#xff0c;OSG于1997年诞生于以为滑翔机爱好者之手&#xff0c;Don burns 为了对滑翔机的飞行进行模拟&#xff0c;对openGL的库进行了封装&#xff0c;osg的雏形就这样诞生了&…...

nodejs基于微信小程序的云校园的设计与实现

摘 要 相比于传统的校园管理方式&#xff0c;智能化的管理方式可以大幅提高校园的管理效率&#xff0c;实现了云校园管理的标准化、制度化、程序化的管理&#xff0c;有效地防止了云校园信息的不规范管理&#xff0c;提高了信息的处理速度和精确度&#xff0c;能够及时、准确地…...

uni-app快速入门(十)--常用内置组件(下)

本文介绍uni-app的textarea多行文本框组件、web-view组件、image图片组件、switch开关组件、audio音频组件、video视频组件。 一、textarea多行文本框组件 textarea组件在HTML 中相信大家非常熟悉&#xff0c;组件的官方介绍见&#xff1a; textarea | uni-app官网uni-app,un…...

golang基础

在 Go 中字符串是不可变的&#xff0c;例如下面的代码编译时会报错&#xff1a; cannot assign to s[0] 但如果真的想要修改怎么办呢&#xff1f;下面的代码可以实现&#xff1a; var s string "hello" s [ 0 ] c s : "hello" c : [] b…...

Selenium + 数据驱动测试:从入门到实战!

引言 在软件测试中&#xff0c;测试数据的多样性和灵活性对测试覆盖率至关重要。而数据驱动测试&#xff08;Data-Driven Testing&#xff09;通过将测试逻辑与数据分离&#xff0c;极大地提高了测试用例的可维护性和可扩展性。本文将结合Selenium这一流行的测试工具&#xff0…...

LLaMA与ChatGLM选用比较

目录 1. 开发背景 2. 目标与应用 3. 训练数据 4. 模型架构与规模 5. 开源与社区支持 6. 对话能力 7. 微调与应用 8. 推理速度与资源消耗 总结 LLaMA(Large Language Model Meta AI)和 ChatGLM(Chat Generative Language Model)都是强大的大型语言模型,但它们有一…...

GPTZero:高效识别AI生成文本,保障学术诚信与内容原创性

产品描述 GPTZero 是一款先进的AI文本检测工具&#xff0c;专为识别由大型语言模型&#xff08;如ChatGPT、GPT-4、Bard等&#xff09;生成的文本而设计。它通过分析文本的复杂性和一致性&#xff0c;判断文本是否可能由人类编写。GPTZero 已经得到了超过100家媒体机构的报道&…...

C/C++ 优化,strlen 示例

目录 C/C optimization, the strlen examplehttps://hallowed-blinker-3ca.notion.site/C-C-optimization-the-strlen-example-108719425da080338d94c79add2bb372 揭开优化的神秘面纱... 让我们来谈谈 CPU 等等&#xff0c;SIMD 是什么&#xff1f; 为什么 strlen 是一个很…...

【动手学深度学习Pytorch】1. 线性回归代码

零实现 导入所需要的包&#xff1a; # %matplotlib inline import random import torch from d2l import torch as d2l import matplotlib.pyplot as plt import matplotlib import os构造人造数据集&#xff1a;假设w[2, -3.4]&#xff0c;b4.2&#xff0c;存在随机噪音&…...

深入理解PyTorch中的卷积层:工作原理、参数解析与实际应用示例

深入理解PyTorch中的卷积层&#xff1a;工作原理、参数解析与实际应用示例 在PyTorch中&#xff0c;卷积层是构建卷积神经网络&#xff08;CNNs&#xff09;的基本单元&#xff0c;广泛用于处理图像和视频中的特征提取任务。通过卷积操作&#xff0c;网络可以有效地学习输入数…...

DataGear 5.2.0 发布,数据可视化分析平台

DataGear 企业版 1.3.0 已发布&#xff0c;欢迎体验&#xff01; http://datagear.tech/pro/ DataGear 5.2.0 发布&#xff0c;图表插件支持定义依赖库、严重 BUG 修复、功能改进、安全增强&#xff0c;具体更新内容如下&#xff1a; 重构&#xff1a;各模块管理功能访问路径…...

uniapp: vite配置rollup-plugin-visualizer进行小程序依赖可视化分析减少vender.js大小

一、前言 在之前文章《uniapp: 微信小程序包体积超过2M的优化方法&#xff08;主包从2.7M优化到1.5M以内&#xff09;》中&#xff0c;提到了6种优化小程序包体积的方法&#xff0c;但并没有涉及如何分析common/vender.js这个文件的优化&#xff0c;而这个文件的大小通常情况下…...

深度学习:如何复现神经网络

深度学习&#xff1a;如何复现神经网络 要复现图中展示的卷积神经网络&#xff08;CNN&#xff09;&#xff0c;我们需详细了解和配置每层网络的功能与设计理由。以下将具体解释各层的配置以及设计选择的原因&#xff0c;确保网络设计的合理性与有效性。 详细的网络层配置与设…...

Spring Boot与MyBatis-Plus的高效集成

Spring Boot与MyBatis-Plus的高效集成 引言 在现代 Java 开发中&#xff0c;MyBatis-Plus 作为 MyBatis 的增强工具&#xff0c;以其简化 CRUD 操作和无需编写 XML 映射文件的特点&#xff0c;受到了开发者的青睐。本篇文章将带你一步步整合 Spring Boot 与 MyBatis-Plus&…...

【Unity ShaderGraph实现流体效果之Function入门】

Unity ShaderGraph实现流体效果之Node入门&#xff08;一&#xff09; 前言Shader Graph NodePosition NodeSplit NodeSubtract NodeBranch Node 总结 前言 Unity 提供的Shader Graph在很大程度上简化了开发者对于编写Shader的工作&#xff0c;只需要拖拽即可完成一个视觉效果…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​&#xff1a; 下载安装DevEco Studio 4.0&#xff08;支持HarmonyOS 5&#xff09;配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​&#xff1a; ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

Docker 本地安装 mysql 数据库

Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker &#xff1b;并安装。 基础操作不再赘述。 打开 macOS 终端&#xff0c;开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...

IP如何挑?2025年海外专线IP如何购买?

你花了时间和预算买了IP&#xff0c;结果IP质量不佳&#xff0c;项目效率低下不说&#xff0c;还可能带来莫名的网络问题&#xff0c;是不是太闹心了&#xff1f;尤其是在面对海外专线IP时&#xff0c;到底怎么才能买到适合自己的呢&#xff1f;所以&#xff0c;挑IP绝对是个技…...