信息学奥赛一本通 1984:【19CSPJ普及组】纪念品 | 洛谷 P5662 [CSP-J2019] 纪念品
【题目链接】
ybt 1984:【19CSPJ普及组】纪念品
洛谷 P5662 [CSP-J2019] 纪念品
【题目考点】
1. 动态规划:完全背包
【解题思路】
由于小伟每天都可以买卖物品无限次,我们可以假想每天开始时,他把所有的商品都卖出,看用手中的钱该买哪些商品。
到第二天,又可以卖出商品换钱了,因此只需要考虑商品在当天及第二天的差价,差价越高,今天买该商品,到第二天升值越多。
结合购买纪念品的背景,每件商品可以购买无限件,因此在第i天买入商品,到第i+1天卖出所有商品,想要赚到最多的钱币,该问题实际是一个完全背包问题。
- 背包容量:小伟第i天拥有的钱币数
- 物品重量:每件物品在第i天的价格
- 物品价值:每件物品第i+1天的价格减去第i天的价格(差价)
- 能装入背包中的所有物品的最大价值:从第i天到第i+1天小伟赚到的钱币数,也就是第i+1天比第i天多获得钱币的最大值。
t为总天数,循环变量i从1循环到t-1,每次循环使用完全背包方法求在第i天买入商品到第i+1天卖出所有商品后多赚到的钱币,在原钱币数量基础上增加赚到钱币的数量,该钱币数量作为下一天购买商品可以使用的总钱数(也就是背包容量)。
最后输出总钱数。
【题解代码】
解法1:完全背包 二维状态
#include <bits/stdc++.h>
using namespace std;
#define N 105
#define M 10005
int p[N][N];//p[i][j]:第i天第j纪念品的价格
int w[N], c[N], dp[N][M];//dp[i][j]:前i个物品中选择物品放入大小为j的背包能获得的最大价值
int main()
{int t, n, m;cin >> t >> n >> m;for(int i = 1; i <= t; ++i)for(int j = 1; j <= n; ++j)cin >> p[i][j];for(int i = 1; i < t; ++i){for(int j = 1; j <= n; ++j){w[j] = p[i][j]; c[j] = p[i+1][j]-p[i][j];}for(int k = 1; k <= n; ++k)for(int j = 1; j <= m; ++j){if(j >= w[k])dp[k][j] = max(dp[k-1][j], dp[k][j-w[k]]+c[k]);elsedp[k][j] = dp[k-1][j];}m += dp[n][m];//总钱数增加相邻两天多赚到的最大钱币数 }cout << m; return 0;
}
解法2:完全背包 滚动数组优化
#include <bits/stdc++.h>
using namespace std;
#define N 105
#define M 10005
int p[N][N];//p[i][j]:第i天第j纪念品的价格
int w[N], c[N], dp[M];//dp[i][j]:前i个物品中选择物品放入大小为j的背包能获得的最大价值
int main()
{int t, n, m;cin >> t >> n >> m;for(int i = 1; i <= t; ++i)for(int j = 1; j <= n; ++j)cin >> p[i][j];for(int i = 1; i < t; ++i){for(int j = 1; j <= n; ++j){w[j] = p[i][j]; c[j] = p[i+1][j]-p[i][j];}memset(dp, 0, sizeof(dp));for(int k = 1; k <= n; ++k)for(int j = w[k]; j <= m; ++j)dp[j] = max(dp[j], dp[j-w[k]]+c[k]);m += dp[m];//总钱数增加相邻两天多赚到的最大钱币数 }cout << m; return 0;
}
相关文章:
信息学奥赛一本通 1984:【19CSPJ普及组】纪念品 | 洛谷 P5662 [CSP-J2019] 纪念品
【题目链接】 ybt 1984:【19CSPJ普及组】纪念品 洛谷 P5662 [CSP-J2019] 纪念品 【题目考点】 1. 动态规划:完全背包 【解题思路】 由于小伟每天都可以买卖物品无限次,我们可以假想每天开始时,他把所有的商品都卖出ÿ…...
JVM——JVM参数指南
文章目录 1.概述2.堆内存相关2.1.显式指定堆内存–Xms和-Xmx2.2.显式新生代内存(Young Ceneration)2.3.显示指定永久代/元空间的大小 3.垃圾收集相关3.1.垃圾回收器3.2.GC记录 1.概述 在本篇文章中,你将掌握最常用的 JVM 参数配置。如果对于下面提到了一些概念比如…...
马上七夕到了,用各种编程语言实现10种浪漫表白方式
目录 1. 直接表白:2. 七夕节表白:3. 猜心游戏:4. 浪漫诗句:5. 爱的方程式:6. 爱心Python:7. 心形图案JavaScript 代码:8. 心形并显示表白信息HTML 页面:9. Java七夕快乐:…...
Spring Clould 注册中心 - Eureka,Nacos
视频地址:微服务(SpringCloudRabbitMQDockerRedis搜索分布式) Eureka 微服务技术栈导学(P1、P2) 微服务涉及的的知识 认识微服务-服务架构演变(P3、P4) 总结: 认识微服务-微服务技…...
使用appuploader工具发布证书和描述性文件教程
使用APPuploader工具发布证书和描述性文件教程 之前用AppCan平台开发了一个应用,平台可以同时生成安卓版和苹果版,想着也把这应用上架到App Store试试,于是找同学借了个苹果开发者账号,但没那么简单,还要用到Mac电脑的…...
【面试八股文】每日一题:谈谈你对IO的理解
谈谈你对IO的理解 每日一题-Java核心-谈谈你对对IO的理解【面试八股文】 1.Java基础知识 Java IO(Input/Output)是Java编程语言中用于处理输入和输出的一组类和接口。它提供了一种在Java程序中读取和写入数据的方法。 Java IO包括两个主要的部分&#x…...
200. 岛屿数量
思路:遍历整个矩阵,对每个格子执行以下操作: 如果格子是陆地(‘1’),则将其标记为已访问(‘0’),并从当前位置开始进行深度优先搜索,将与当前格子相邻的陆地都…...
【LeetCode】581.最短无序连续子数组
题目 给你一个整数数组 nums ,你需要找出一个 连续子数组 ,如果对这个子数组进行升序排序,那么整个数组都会变为升序排序。 请你找出符合题意的 最短 子数组,并输出它的长度。 示例 1: 输入:nums [2,6…...
曲面(弧面、柱面)展平(拉直)瓶子标签识别ocr
瓶子或者柱面在做字符识别的时候由于变形,识别效果是很不好的 或者是检测瓶子表面缺陷的时候效果也没有展平的好 下面介绍两个项目,关于曲面(弧面、柱面)展平(拉直) 项目一:通过识别曲面的6个点…...
知识继承概述
文章目录 知识继承第一章 知识继承概述1.背景介绍第一页 背景第二页 大模型训练成本示例第三页 知识继承的动机 2.知识继承的主要方法 第二章 基于知识蒸馏的知识继承预页 方法概览 1.知识蒸馏概述第一页 知识蒸馏概述第二页 知识蒸馏第三页 什么是知识第四页 知识蒸馏的核心目…...
深度剖析数据在内存中的存储
目录 一、数据类型介绍 类型的基本归类 1.整形家族 2.浮点数家族 3.构造类型 (自定义类型) 4.指针类型 5.空类型 二、整形在内存中的存储 1.原码、反码、补码 1.1原码 1.2反码 1.3补码 1.4计算规则 2 .大小端介绍 三、浮点型在内存中的存…...
【ARM Linux 系统稳定性分析入门及渐进10 -- GDB 初始化脚本介绍及使用】
文章目录 gdb 脚本介绍gdb 初始化脚本使用启动 gdb 的时候自动执行脚本gdb运行期间执行命令脚本 gdb 脚本介绍 GDB脚本是一种使用GDB命令语言编写的脚本,可以用来自动化一些常见的调试任务。这些脚本可以直接在GDB中运行,也可以通过GDB的-x参数或source…...
AQS源码解读
文章目录 前言一、AQS是什么?二、解读重点属性statehead、tail 同步变量竞争acquire 同步变量释放 总结 前言 AQS是AbstractQueuedSynchronizer的缩写,也是大神Doug Lea的得意之作。今天我们来进行尽量简化的分析和理解性的代码阅读。 一、AQS是什么&am…...
QT实现天气预报
1. MainWindow类设计的成员变量和方法 public: MainWindow(QWidget* parent nullptr); ~MainWindow(); protected: 形成文本菜单来用来右键关闭窗口 void contextMenuEvent(QContextMenuEvent* event); 鼠标被点击之后此事件被调用 void mousePressEvent(QMouseEv…...
【马蹄集】第二十三周——进位制专题
进位制专题 目录 MT2186 二进制?不同!MT2187 excel的烦恼MT2188 单条件和MT2189 三进制计算机1MT2190 三进制计算机2 MT2186 二进制?不同! 难度:黄金 时间限制:1秒 占用内存:128M 题目…...
[足式机器人]Part3 变分法Ch01-1 数学预备知识——【读书笔记】
本文仅供学习使用 本文参考: 《变分法基础-第三版》老大中 《变分学讲义》张恭庆 《Calculus of Variations of Optimal Control Theory》-变分法和最优控制论-Daneil Liberzon Ch01-1 数学基础-预备知识1 1 数学基础-预备知识1.1 泰勒公式1.1.1 一元函数的泰勒公式…...
计算机网络----CRC冗余码的运算
目录 1. 冗余码的介绍及原理2. CRC检验编码的例子3. 小练习 1. 冗余码的介绍及原理 冗余码是用于在数据链路层的通信链路和传输数据过程中可能会出错的一种检错编码方法(检错码)。原理:发送发把数据划分为组,设每组K个比特&#…...
将Nginx源码数组结构(ngx_array.c)和内存池代码单独编译运行,附代码
在上面一篇的基础上把Nginx源码数组结构也摘录下来,也增加了测试代码,编译运行。 https://blog.csdn.net/katerdaisy/article/details/132358883 《将nginx内存池代码单独编译运行,了解nginx内存池工作原理,附代码》 核心代码&…...
java forEach中不能使用break和continue的原因
1.首先了解break和continue的使用范围和作用 1.1使用范围 break适用范围:只能用于switch或者是循环语句中。当然可以用于增强for循环。 continue适用范围: 用于循环语句中。 1.2作用 break: 1. break用于switch语句的作用是结束一个switch语句。 2. break用于循…...
[杂项]水浒英雄谱系列电影列表
年份 片名 导演 主演 2006-01-01 母夜叉孙二娘 张建亚 周海媚 、 莫少聪 、 于承惠 [1] 2008-01-01 碧瑶霜迷案 黄祖权 陈龙 、 陈德容 、 翁家明 [7] 2008-05-09 青面兽杨志 张建亚 吕良伟 、 计春华 、 孟广美 [2] 2008-05-09 扈三娘与矮脚虎王英 张建亚 曾宝仪 、 郭德纲 、…...
RestClient
什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级ÿ…...
基于服务器使用 apt 安装、配置 Nginx
🧾 一、查看可安装的 Nginx 版本 首先,你可以运行以下命令查看可用版本: apt-cache madison nginx-core输出示例: nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...
《通信之道——从微积分到 5G》读书总结
第1章 绪 论 1.1 这是一本什么样的书 通信技术,说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号(调制) 把信息从信号中抽取出来&am…...
【单片机期末】单片机系统设计
主要内容:系统状态机,系统时基,系统需求分析,系统构建,系统状态流图 一、题目要求 二、绘制系统状态流图 题目:根据上述描述绘制系统状态流图,注明状态转移条件及方向。 三、利用定时器产生时…...
第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词
Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵,其中每行,每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid,其中有多少个 3 3 的 “幻方” 子矩阵&am…...
C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。
1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj,再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...
AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机
这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机,因为在使用过程中发现 Airsim 对外部监控相机的描述模糊,而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置,最后在源码示例中找到了,所以感…...
Chrome 浏览器前端与客户端双向通信实战
Chrome 前端(即页面 JS / Web UI)与客户端(C 后端)的交互机制,是 Chromium 架构中非常核心的一环。下面我将按常见场景,从通道、流程、技术栈几个角度做一套完整的分析,特别适合你这种在分析和改…...
Qt的学习(一)
1.什么是Qt Qt特指用来进行桌面应用开发(电脑上写的程序)涉及到的一套技术Qt无法开发网页前端,也不能开发移动应用。 客户端开发的重要任务:编写和用户交互的界面。一般来说和用户交互的界面,有两种典型风格&…...
HTTPS证书一年多少钱?
HTTPS证书作为保障网站数据传输安全的重要工具,成为众多网站运营者的必备选择。然而,面对市场上种类繁多的HTTPS证书,其一年费用究竟是多少,又受哪些因素影响呢? 首先,HTTPS证书通常在PinTrust这样的专业平…...
