当前位置: 首页 > 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;只需要拖拽即可完成一个视觉效果…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装&#xff1b;只需暴露 19530&#xff08;gRPC&#xff09;与 9091&#xff08;HTTP/WebUI&#xff09;两个端口&#xff0c;即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

Linux 内存管理实战精讲:核心原理与面试常考点全解析

Linux 内存管理实战精讲&#xff1a;核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用&#xff0c;还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...

动态 Web 开发技术入门篇

一、HTTP 协议核心 1.1 HTTP 基础 协议全称 &#xff1a;HyperText Transfer Protocol&#xff08;超文本传输协议&#xff09; 默认端口 &#xff1a;HTTP 使用 80 端口&#xff0c;HTTPS 使用 443 端口。 请求方法 &#xff1a; GET &#xff1a;用于获取资源&#xff0c;…...

Selenium常用函数介绍

目录 一&#xff0c;元素定位 1.1 cssSeector 1.2 xpath 二&#xff0c;操作测试对象 三&#xff0c;窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四&#xff0c;弹窗 五&#xff0c;等待 六&#xff0c;导航 七&#xff0c;文件上传 …...