GESP认证C++编程真题解析 | B3873 [GESP202309 六级] 小杨买饮料

​欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

• 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
• 希望系统学习C++/Python编程的初学者
• 想要提升算法与编程能力的编程爱好者

附上汇总帖：GESP认证C++编程真题解析 | 汇总

【题目来源】

洛谷：[B3873 GESP202309 六级] 小杨买饮料 - 洛谷

【题目描述】

小杨来到了一家商店，打算购买一些饮料。这家商店总共出售N NN种饮料，编号从0 00至N − 1 N-1N−1，其中编号为i ii的饮料售价c i c_ici​元，容量l i l_ili​毫升。

小杨的需求有如下几点：

1. 小杨想要尽可能尝试不同种类的饮料，因此他希望每种饮料至多购买1 11瓶；
2. 小杨很渴，所以他想要购买总容量不低于L LL的饮料；
3. 小杨勤俭节约，所以在1 11和2 22的前提下，他希望使用尽可能少的费用。

方便起见，你只需要输出最少花费的费用即可。特别地，如果不能满足小杨的要求，则输出no solution。

【输入】

第一行两个整数N , L N,LN,L。

接下来N NN行，依次描述第i = 0 , 1 , ⋯ , N − 1 i=0,1,\cdots,N-1i=0,1,⋯,N−1种饮料：每行两个整数c i , l i c_i,l_ici​,li​。

【输出】

输出一行一个整数，表示最少需要花费多少钱，才能满足小杨的要求。特别地，如果不能满足要求，则输出no solution。

【输入样例】

5 100 100 2000 2 50 4 40 5 30 3 20

【输出样例】

9

【算法标签】

《洛谷 B3873 小杨买饮料》 #动态规划DP# #背包DP# #GESP# #2023#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=505;// 最大物品数量constintINF=0x3f3f3f3f;// 定义无穷大intn,L;// n: 物品数量, L: 最小需要的长度intc[N],l[N];// c[i]: 第i个物品的价格, l[i]: 第i个物品的长度intdp[1000005];// dp[j]: 总长度至少为j时的最小花费intmain(){// 输入物品数量和需要的最小长度cin>>n>>L;// 输入每个物品的价格和长度for(inti=1;i<=n;i++){cin>>c[i]>>l[i];}// 初始化dp数组为无穷大memset(dp,0x3f,sizeof(dp));dp[0]=0;// 总长度为0时的最小花费为0// 动态规划：0-1背包的变形（至少型背包）for(inti=1;i<=n;i++)// 遍历每个物品{for(intj=1000000;j>=l[i];j--)// 从大到小遍历，保证每个物品只用一次{// 状态转移方程：// 不选当前物品：dp[j] 保持不变// 选当前物品：dp[j-l[i]] + c[i]// 取两者最小值dp[j]=min(dp[j],dp[j-l[i]]+c[i]);}}// 在满足长度至少为L的所有方案中寻找最小花费intans=INF;for(inti=L;i<=1000000;i++){ans=min(ans,dp[i]);}// 输出结果if(ans==INF){// 没有找到满足条件的方案cout<<"no solution"<<endl;}else{// 输出最小花费cout<<ans<<endl;}return0;}

【运行结果】

5 100 100 2000 2 50 4 40 5 30 3 20 9