洛谷P5662纪念品一题 的题解
由于此题是CSP-J考场上的一道题我们不妨先假设自己是一名菜鸟考生用一些比较新鲜的角度去做题。正文考试时会先干嘛呢那一定是去看数据范围。CSP比GESP好的点就在于它不会让你输得太难看总有几分是你水得到的。显然这里有10%的数据是很轻松就能做对的就是当T1即小伟的神力有但完全没用只能预测一天时他买纪念品却不能以更高的价格卖出因为当天的价格是不变的类似于炒股所以他最后所持有的金币数与他最开始拥有的金币数是一样的。这里就先不给代码了。相信大家都是比我厉害的大佬当然只水十分不太对得起我们辛苦的思考考虑到T100N1时有15%的数据意思是超能力持续天数变多但是只有一种商品所以操作就是如果明天价格更贵就用今天的钱买尽量多的纪念品第二天再卖掉所以第二天后手里有的金币数就该是今天能买到的*明天价格今天余数对应的代码如下intansm;for(inti0;it;i){if(p[i1][0]p[i][0]){intcntans/p[i][0];ansans%p[i][0]cnt*p[i1][0];}}coutans;进一步地我们还能看到有15%的数据是T2也就是超能力持续两天刚好够做一次交易。这时我们先来捋一捋思路小伟手中金币数一定也就是只能选择部分纪念品进行买卖每种纪念品可以购买无数次钱够最后使得第二天卖出时利益最大不难看出这是一个简单的完全背包问题手里钱数是背包容量今天的价格对应物品体积明天价格则是物品价值然后直接套完全背包模板就可以了。如果第二天价格比今天还便宜直接continue掉实际上这里做出来后就很接近最后的AC代码了因为取的是特殊值两天我们就可以尝试把这T天分成两天一次的背包即今天和明天明天和后天…以此类推要进行T-1次不过每天都要更新手里的金币数。完整代码#includebits/stdc.husingnamespacestd;intn,m,t;intp[105][105];voidcheck1(){intansm;for(inti0;it;i){if(p[i1][0]p[i][0]){intcntans/p[i][0];ansans%p[i][0]cnt*p[i1][0];}}coutans;}voidcheck2(){intdp[1000005];memset(dp,0,sizeof(dp));for(inti0;in;i){intcostp[0][i];intvp[1][i]-cost;if(v0){continue;}for(intjcost;jm;j){dp[j]max(dp[j],dp[j-cost]v);}}coutmdp[m];}voidcheck3(){intdp[100005];for(intd0;dt-1;d){memset(dp,0,sizeof(dp));for(inti0;in;i){intcostp[d][i];intvp[d1][i]-cost;if(v0){continue;}for(intjcost;jm;j){dp[j]max(dp[j],dp[j-cost]v);}}mdp[m];}coutm;}intmain(){cintnm;for(inti0;it;i){for(intj0;jn;j){cinp[i][j];}}if(t1){coutm;return0;}if(n1){check1();return0;}if(t2){check2();return0;}//以上是前面的骗分环节只保留check3也行check3();return0;}注老师作业要求不喜勿喷

相关新闻

HarmonyOS NEXT 企业级记账APP:Canvas 绘制折线图

HarmonyOS NEXT 企业级记账APP:Canvas 绘制折线图

想# Canvas 绘制折线图 本文是《HarmonyOS NEXT 企业级开发实战:30篇打造智能记账APP》系列的第 21 篇,对应 Git Tag v0.2.1。承接前篇饼图与柱状图,本篇使用 Canvas API 绘制折线图展示收支趋势曲线,封装 LineChart 组件支持折线…

2026/8/3 9:41:57 阅读更多 →
DML 表数据:插入、删除、修改

DML 表数据:插入、删除、修改

1.SQL语言表数据插入 语法1:指定字段插入(推荐) insert into 表名(字段1,字段2,...) values(值1,值2,...);示例 create table user(id int primary key auto_increment,name varchar(20) not null,age int );insert into user(name, age) …

2026/8/3 11:46:06 阅读更多 →
开关电源EMC整改实战:从噪声源头到PCB布局与滤波器设计

开关电源EMC整改实战:从噪声源头到PCB布局与滤波器设计

1. 从一次深夜的EMC测试失败说起凌晨两点,实验室里只剩下示波器的蜂鸣声和频谱分析仪屏幕上刺眼的红色超标曲线。眼前的这款24V/5A反激式开关电源,在传导骚扰(CE)测试中,150kHz到30MHz的频段上,像一座座连绵…

2026/8/3 18:18:21 阅读更多 →

最新新闻

Android 13屏幕亮度调整:利用Overlay机制定制背光参数

Android 13屏幕亮度调整:利用Overlay机制定制背光参数

1. 项目背景与核心诉求 最近在折腾一台基于Android 13的设备,发现它的屏幕背光亮度调节范围不太理想。最低亮度在暗光环境下还是有点刺眼,而最高亮度在户外阳光下又感觉不够亮,看不太清。这其实是一个挺常见的问题,很多设备的默认…

2026/8/3 21:56:30 阅读更多 →
Dango-Translator深度解析:三分钟掌握全能OCR翻译工具的核心使用技巧

Dango-Translator深度解析:三分钟掌握全能OCR翻译工具的核心使用技巧

Dango-Translator深度解析:三分钟掌握全能OCR翻译工具的核心使用技巧 【免费下载链接】Dango-Translator 梦想是做出最棒的生肉翻译软件喵 项目地址: https://gitcode.com/GitHub_Trending/da/Dango-Translator Dango-Translator(团子翻译器&…

2026/8/3 21:56:30 阅读更多 →
python的工业过程控制场景模拟第四十七篇:统计调节阀动作频次,预判密封件磨损周期,实现预测性维护。

python的工业过程控制场景模拟第四十七篇:统计调节阀动作频次,预判密封件磨损周期,实现预测性维护。

调节阀动作频次统计与密封件磨损预测系统 —— 基于 OOP 的预测性维护实战"调节阀是流程工业的关节。它不像泵那样轰鸣,也不像反应器那样引人注目,但它一直在动——每一次调节都是对密封件的折磨。等到现场发现内漏再去拆检,往往已经晚了…

2026/8/3 21:56:30 阅读更多 →
HTMLx工具链实战:从智能生成到构建优化的前端开发新范式

HTMLx工具链实战:从智能生成到构建优化的前端开发新范式

1. 项目概述:HTMLx是什么,以及为什么你需要关注它 如果你是一名前端开发者,或者哪怕只是偶尔需要和网页代码打交道的运营、内容创作者,那么“HTMLx”这个名字,很可能在最近已经悄然进入了你的视野。它不是一个全新的编…

2026/8/3 21:56:30 阅读更多 →
TRELLIS.2性能优化:CUDA加速下的毫秒级网格转换技巧

TRELLIS.2性能优化:CUDA加速下的毫秒级网格转换技巧

TRELLIS.2性能优化:CUDA加速下的毫秒级网格转换技巧 【免费下载链接】TRELLIS.2 Native and Compact Structured Latents for 3D Generation 项目地址: https://gitcode.com/GitHub_Trending/tr/TRELLIS.2 TRELLIS.2是一款专注于3D生成的开源项目&#xff0c…

2026/8/3 21:56:30 阅读更多 →
CTF竞赛中的GIF隐写术与多层解码实战

CTF竞赛中的GIF隐写术与多层解码实战

1. 项目概述:Misc与CTF中的GIF隐写术在CTF(Capture The Flag)竞赛的杂项(Misc)分类中,GIF文件分析一直是经典题型。"攻防世界"平台上的"gif如来十三掌"题目结合了图像隐写和传统密码学…

2026/8/3 21:55:30 阅读更多 →

日新闻

3个让你工作效率翻倍的Umi-OCR实战技巧:免费离线文字识别完全指南

3个让你工作效率翻倍的Umi-OCR实战技巧:免费离线文字识别完全指南

3个让你工作效率翻倍的Umi-OCR实战技巧:免费离线文字识别完全指南 【免费下载链接】Umi-OCR OCR software, free and offline. 开源、免费的离线OCR软件。支持截屏/批量导入图片,PDF文档识别,排除水印/页眉页脚,扫描/生成二维码。…

2026/8/3 0:00:47 阅读更多 →
[具身智能-181]:PC+服务器+具身机器人:构建具身智能从仿真到量产的闭环迭代混合架构

[具身智能-181]:PC+服务器+具身机器人:构建具身智能从仿真到量产的闭环迭代混合架构

PC服务器具身机器人:构建具身智能从仿真到量产的闭环迭代混合架构一、前言:具身智能需要“混合算力闭环系统”传统人工智能依赖云端静态数据集训练,不具备物理交互能力,无法适应真实世界的不确定性。具身智能(Embodied…

2026/8/3 0:00:47 阅读更多 →
[具身智能-181]:大分布式通信模型对比:看懂为什么 DDS 是 ROS2 底层通信最优解

[具身智能-181]:大分布式通信模型对比:看懂为什么 DDS 是 ROS2 底层通信最优解

前言构建机器人、具身智能这类分布式实时系统,通信底座直接决定整套系统的实时性、容错性、组网能力。分布式领域长期存在 4 类经典通信架构:点对点模式、Broker 中间代理模式、广播模式、以数据为中心(DDS)模式。很多开发者疑惑&…

2026/8/3 0:00:47 阅读更多 →

周新闻

最大流算法详解:从水管网络到Ford-Fulkerson与Dinic实战

最大流算法详解:从水管网络到Ford-Fulkerson与Dinic实战

1. 从水管网络到最大流:一个核心问题的诞生想象一下,你是一个城市供水系统的总工程师。你的城市有多个水源(水库),需要通过一个复杂的地下管道网络,将水输送到各个居民区。每条管道都有其最大通水能力&…

2026/8/3 4:58:13 阅读更多 →
基于Springboot的企业门户网站(源码+LW+调试文档+讲解)

基于Springboot的企业门户网站(源码+LW+调试文档+讲解)

温馨提示:本人主页置顶文章(点我)开头有 CSDN 平台官方提供的学长联系方式的名片! 温馨提示:本人主页置顶文章(点我)开头有 CSDN 平台官方提供的学长联系方式的名片! 温馨提示:本人主页置顶文章(点我)开头有 CSDN 平台…

2026/8/3 1:53:31 阅读更多 →
MATLAB xcorr函数详解:从互相关原理到四大实战应用

MATLAB xcorr函数详解:从互相关原理到四大实战应用

1. 从一次信号“找茬”说起:为什么我们需要互相关几年前,我在处理一组声学传感器数据时遇到了一个棘手的问题。我有两个麦克风记录了一段相同的音频信号,理论上它们接收到的声音波形应该非常相似,只是由于麦克风位置不同&#xff…

2026/8/3 4:36:35 阅读更多 →

月新闻

免费解锁百度网盘SVIP加速:macOS用户必备的下载提速终极指南

免费解锁百度网盘SVIP加速:macOS用户必备的下载提速终极指南

免费解锁百度网盘SVIP加速:macOS用户必备的下载提速终极指南 【免费下载链接】BaiduNetdiskPlugin-macOS For macOS.百度网盘 破解SVIP、下载速度限制~ 项目地址: https://gitcode.com/gh_mirrors/ba/BaiduNetdiskPlugin-macOS 还在为百度网盘macOS版的龟速下…

2026/8/3 13:07:03 阅读更多 →
终极ncmdump指南:3分钟实现网易云NCM音乐解密与格式转换

终极ncmdump指南:3分钟实现网易云NCM音乐解密与格式转换

终极ncmdump指南:3分钟实现网易云NCM音乐解密与格式转换 【免费下载链接】ncmdump 项目地址: https://gitcode.com/gh_mirrors/ncmd/ncmdump 还在为网易云音乐下载的NCM格式文件无法在其他播放器播放而烦恼吗?ncmdump解密工具帮你轻松解决这个困…

2026/8/3 5:19:38 阅读更多 →
HarmonyOS 应用开发《掌上英语》第81篇: 智能体卡片:为英语学习 App 打造桌面级学习助手

HarmonyOS 应用开发《掌上英语》第81篇: 智能体卡片:为英语学习 App 打造桌面级学习助手

AgentCard 智能体卡片:为英语学习 App 打造桌面级学习助手适用平台:HarmonyOS 7.0 (API 26 Beta)一、引言 HarmonyOS 7.0(API 26 Beta)新增了 AgentCard 智能体卡片能力,这是继 HMAF(鸿蒙智能体框架&#x…

2026/8/3 8:27:36 阅读更多 →