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

信息学奥赛一本通 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&#xff1a;【19CSPJ普及组】纪念品 洛谷 P5662 [CSP-J2019] 纪念品 【题目考点】 1. 动态规划&#xff1a;完全背包 【解题思路】 由于小伟每天都可以买卖物品无限次&#xff0c;我们可以假想每天开始时&#xff0c;他把所有的商品都卖出&#xff…...

JVM——JVM参数指南

文章目录 1.概述2.堆内存相关2.1.显式指定堆内存–Xms和-Xmx2.2.显式新生代内存(Young Ceneration)2.3.显示指定永久代/元空间的大小 3.垃圾收集相关3.1.垃圾回收器3.2.GC记录 1.概述 在本篇文章中&#xff0c;你将掌握最常用的 JVM 参数配置。如果对于下面提到了一些概念比如…...

马上七夕到了,用各种编程语言实现10种浪漫表白方式

目录 1. 直接表白&#xff1a;2. 七夕节表白&#xff1a;3. 猜心游戏&#xff1a;4. 浪漫诗句&#xff1a;5. 爱的方程式&#xff1a;6. 爱心Python&#xff1a;7. 心形图案JavaScript 代码&#xff1a;8. 心形并显示表白信息HTML 页面&#xff1a;9. Java七夕快乐&#xff1a;…...

Spring Clould 注册中心 - Eureka,Nacos

视频地址&#xff1a;微服务&#xff08;SpringCloudRabbitMQDockerRedis搜索分布式&#xff09; Eureka 微服务技术栈导学&#xff08;P1、P2&#xff09; 微服务涉及的的知识 认识微服务-服务架构演变&#xff08;P3、P4&#xff09; 总结&#xff1a; 认识微服务-微服务技…...

使用appuploader工具发布证书和描述性文件教程

使用APPuploader工具发布证书和描述性文件教程 之前用AppCan平台开发了一个应用&#xff0c;平台可以同时生成安卓版和苹果版&#xff0c;想着也把这应用上架到App Store试试&#xff0c;于是找同学借了个苹果开发者账号&#xff0c;但没那么简单&#xff0c;还要用到Mac电脑的…...

【面试八股文】每日一题:谈谈你对IO的理解

谈谈你对IO的理解 每日一题-Java核心-谈谈你对对IO的理解【面试八股文】 1.Java基础知识 Java IO&#xff08;Input/Output&#xff09;是Java编程语言中用于处理输入和输出的一组类和接口。它提供了一种在Java程序中读取和写入数据的方法。 Java IO包括两个主要的部分&#x…...

200. 岛屿数量

思路&#xff1a;遍历整个矩阵&#xff0c;对每个格子执行以下操作&#xff1a; 如果格子是陆地&#xff08;‘1’&#xff09;&#xff0c;则将其标记为已访问&#xff08;‘0’&#xff09;&#xff0c;并从当前位置开始进行深度优先搜索&#xff0c;将与当前格子相邻的陆地都…...

【LeetCode】581.最短无序连续子数组

题目 给你一个整数数组 nums &#xff0c;你需要找出一个 连续子数组 &#xff0c;如果对这个子数组进行升序排序&#xff0c;那么整个数组都会变为升序排序。 请你找出符合题意的 最短 子数组&#xff0c;并输出它的长度。 示例 1&#xff1a; 输入&#xff1a;nums [2,6…...

曲面(弧面、柱面)展平(拉直)瓶子标签识别ocr

瓶子或者柱面在做字符识别的时候由于变形&#xff0c;识别效果是很不好的 或者是检测瓶子表面缺陷的时候效果也没有展平的好 下面介绍两个项目&#xff0c;关于曲面&#xff08;弧面、柱面&#xff09;展平&#xff08;拉直&#xff09; 项目一&#xff1a;通过识别曲面的6个点…...

知识继承概述

文章目录 知识继承第一章 知识继承概述1.背景介绍第一页 背景第二页 大模型训练成本示例第三页 知识继承的动机 2.知识继承的主要方法 第二章 基于知识蒸馏的知识继承预页 方法概览 1.知识蒸馏概述第一页 知识蒸馏概述第二页 知识蒸馏第三页 什么是知识第四页 知识蒸馏的核心目…...

深度剖析数据在内存中的存储

目录 一、数据类型介绍 类型的基本归类 1.整形家族 2.浮点数家族 3.构造类型 &#xff08;自定义类型&#xff09; 4.指针类型 5.空类型 二、整形在内存中的存储 1.原码、反码、补码 1.1原码 1.2反码 1.3补码 1.4计算规则 2 .大小端介绍 三、浮点型在内存中的存…...

【ARM Linux 系统稳定性分析入门及渐进10 -- GDB 初始化脚本介绍及使用】

文章目录 gdb 脚本介绍gdb 初始化脚本使用启动 gdb 的时候自动执行脚本gdb运行期间执行命令脚本 gdb 脚本介绍 GDB脚本是一种使用GDB命令语言编写的脚本&#xff0c;可以用来自动化一些常见的调试任务。这些脚本可以直接在GDB中运行&#xff0c;也可以通过GDB的-x参数或source…...

AQS源码解读

文章目录 前言一、AQS是什么&#xff1f;二、解读重点属性statehead、tail 同步变量竞争acquire 同步变量释放 总结 前言 AQS是AbstractQueuedSynchronizer的缩写&#xff0c;也是大神Doug Lea的得意之作。今天我们来进行尽量简化的分析和理解性的代码阅读。 一、AQS是什么&am…...

QT实现天气预报

1. MainWindow类设计的成员变量和方法 public: MainWindow(QWidget* parent nullptr); ~MainWindow(); protected: 形成文本菜单来用来右键关闭窗口 void contextMenuEvent(QContextMenuEvent* event); 鼠标被点击之后此事件被调用 void mousePressEvent(QMouseEv…...

【马蹄集】第二十三周——进位制专题

进位制专题 目录 MT2186 二进制&#xff1f;不同&#xff01;MT2187 excel的烦恼MT2188 单条件和MT2189 三进制计算机1MT2190 三进制计算机2 MT2186 二进制&#xff1f;不同&#xff01; 难度&#xff1a;黄金    时间限制&#xff1a;1秒    占用内存&#xff1a;128M 题目…...

[足式机器人]Part3 变分法Ch01-1 数学预备知识——【读书笔记】

本文仅供学习使用 本文参考&#xff1a; 《变分法基础-第三版》老大中 《变分学讲义》张恭庆 《Calculus of Variations of Optimal Control Theory》-变分法和最优控制论-Daneil Liberzon Ch01-1 数学基础-预备知识1 1 数学基础-预备知识1.1 泰勒公式1.1.1 一元函数的泰勒公式…...

计算机网络----CRC冗余码的运算

目录 1. 冗余码的介绍及原理2. CRC检验编码的例子3. 小练习 1. 冗余码的介绍及原理 冗余码是用于在数据链路层的通信链路和传输数据过程中可能会出错的一种检错编码方法&#xff08;检错码&#xff09;。原理&#xff1a;发送发把数据划分为组&#xff0c;设每组K个比特&#…...

将Nginx源码数组结构(ngx_array.c)和内存池代码单独编译运行,附代码

在上面一篇的基础上把Nginx源码数组结构也摘录下来&#xff0c;也增加了测试代码&#xff0c;编译运行。 https://blog.csdn.net/katerdaisy/article/details/132358883 《将nginx内存池代码单独编译运行&#xff0c;了解nginx内存池工作原理&#xff0c;附代码》 核心代码&…...

java forEach中不能使用break和continue的原因

1.首先了解break和continue的使用范围和作用 1.1使用范围 break适用范围&#xff1a;只能用于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 扈三娘与矮脚虎王英 张建亚 曾宝仪 、 郭德纲 、…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

动态 Web 开发技术入门篇

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

JavaScript 数据类型详解

JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型&#xff08;Primitive&#xff09; 和 对象类型&#xff08;Object&#xff09; 两大类&#xff0c;共 8 种&#xff08;ES11&#xff09;&#xff1a; 一、原始类型&#xff08;7种&#xff09; 1. undefined 定…...

Linux nano命令的基本使用

参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时&#xff0c;显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障

关键领域软件测试的"安全密码"&#xff1a;Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力&#xff0c;从金融交易到交通管控&#xff0c;这些关乎国计民生的关键领域…...

nnUNet V2修改网络——暴力替换网络为UNet++

更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...