CSP 2019 第三题：纪念品-北京尧图网络

CSP 2019 第三题纪念品题目链接题目题意数据给出能预测的天数纪念品种类持有金币。每天对金币进行买卖求买卖后的金币最大值如何赚得更多知识点考动态规划思路按照题意能够知道赚得最多就是保证每天都赚最多就行。最简单想法就是第二天根据某纪念品的涨幅先买涨价最多的如果持有金币还有就继续买涨价次之的币种可以结构体排序然后根据剩余一次购买。这个方法真的很贪心每次都是买“性价比”最高的但是这个方法只能局部最优举个例子我有100元某个纪念品初值25元能赚6元另一个纪念品初值20元能赚5元。按照贪心算法定是要买赚8元的只赚6424元但是如果我买初值20元的就是5*525。所以这个时候看出来明显不是最优的。所以贪心算法求最值问题时不一定能办到全部最优个别样例倒是能过。涉及最值问题存在重叠子问题时优先想到用动态规划来做。物品可选一个或者多个是完全背包板子用得上唯一加了点难度就是同一天交易的物品是多个dp[j]表示第i天金币为j时的交易所得最大值因此只需要再完全背包基础上再遍历当天的所有物品金币为j时若“再买一次该纪念品”判断是买当前纪念品是否能“赚钱”状态转移方程-明确状态每天根据买卖金币会变化根据金币大小选择买不买当天纪念品-明确选择每天选择买卖时通常是判断买某个纪念品后的利润买之前持有金币的利润是否变大每次买一个纪念品这样遍历时就能判断是买纪念品A还是买纪念品B划算而不是以为的买涨幅最大的纪念品-明确数组或者dp函数定义所以置数组dp[i]一维数组放每天金币为i时能求的利润最值就行数据约束数据相对比较小注意数组范围100就行代码注意如果是边输入数据边处理是否购买那么i一定是从1开始并且要处理第0排的数据(第一天不可能会产生利润)否则一开始dp数据就会不准确如果输入完数据遍历时i就从第二排开始就行最后每行处理完要初始化我们的dp数组参考代码#includebits/stdc.h#defineMAX_N105usingnamespacestd;inta[MAX_N][MAX_N];//动态规划思想处理intdp[10005]{0};//结果只和金币m有关,dp[i]表示持有i个金币时利润最大值intmain(){intt,n,m;cintnm;memset(a,0x3f,sizeof(a));//也可以不初始化但是后面第一行不赚钱需要特判for(inti1;it;i){for(intj1;jn;j){cina[i][j];intk0a[i][j]-a[i-1][j];//差值0有利润才做记录if(k00){for(intpa[i-1][j];pm;p){//至少要a[i-1][j]个金币才能购买记录最低需要的金币到金币m区间买该金币后的收益dp[p]max(dp[p],dp[p-a[i-1][j]]k0);//买之前的利润(当前金币下的最有买法)和买之后的利润做对比}}}mdp[m];// 初始化结构体memset(dp,0,sizeof(dp));//每一行遍历完后就重置数组}coutm;return0;}贪心算法试了一下果然是样例很多不会过仅35%不能AC贪心算法如下#includebits/stdc.h#defineMAX_N105usingnamespacestd;inta[MAX_N][MAX_N];//定义一个结构体数组储存金币差值和上一天的金币价格金币遍历从差值最高的开始structstu{intk;//记录差值intm0;}s[MAX_N];intcmp(stu st1,stu st2){returnst1.kst2.k;}intmain(){intt,n,m,mm1e4;//mm存储一行的最小值cintnm;// 处理第0排数据memset(a,1e4,sizeof(a));for(inti1;it;i){for(intj1;jn;j){cina[i][j];if(j-10){intk0a[i][j]-a[i-1][j];//差值0才做记录if(k00){s[j].kk0;//差值s[j].m0a[i-1][j];//上一个数据的值if(a[i-1][j]mm)mma[i-1][j];}}}sort(s1,sn,cmp);intnum0,earn0;//赚到的最多的金币可能还能买到的intbeleftm,p1;while(beleftmmpn){if(belefts[p].m0s[p].k0){numbeleft/s[p].m0;earnnum*s[p].k;beleft-num*s[p].m0;}p;}mearn;mm1e4;//初始化;// 初始化结构体memset(s,0,sizeof(s));}coutm;return0;}

CSP 2019 第三题：纪念品

相关推荐

PhysX刚体系统深度解析：从Actor到Shape

October CMS Scoreboard 组件完全指南：在 Laravel 后端界面构建数据总览看板

PhysX 一帧模拟的真实工作：流程、作用与职责

更多资讯

MPC-HC 媒体播放器配置指南：硬件解码加速与字幕加载的正确姿势

VSCodium 使用入门：VS Code 开源无遥测构建的安装配置与插件商店方案

pytest+requests 接口自动化测试实战：REST API 全方法覆盖与用例设计

大学生创新创业训练计划实战：商业计划书框架、路演逻辑与可行性分析要点

市面上最智能的个人物品管理工具

不写一行框架，纯 urllib 调通蓝耘元生代 MaaS：一次终端里的 API 深度实测

今日更新

Agent Skills 完全指南：原理、写法、安装与实战避坑

Agent Skills 实战：从 Genkit 定义到 GKE 部署与排查

Agent Skills 实战：从设计到调试的完整指南

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？