企业官网建设流程全解析

如何自己做网站界面,阿里巴巴外贸订单网站,郑州短视频拍摄制作公司,微信小程序开发教程 下载2024年12月GESP真题及题解(C七级): 武器购买 题目描述 商店里有 nnn 个武器#xff0c;第 iii 个武器的强度为 pip_ipi​#xff0c;花费为 cic_ici​。 小杨想要购买一些武器#xff0c;满足这些武器的总强度不小于 PPP#xff0c;总花费不超过 QQQ#xff0c;小杨想知…2024年12月GESP真题及题解(C七级): 武器购买题目描述商店里有n nn个武器第i ii个武器的强度为p i p_ipi​花费为c i c_ici​。小杨想要购买一些武器满足这些武器的总强度不小于P PP总花费不超过Q QQ小杨想知道是否存在满足条件的购买方案如果有最少花费又是多少。输入格式第一行包含一个正整数t tt代表测试数据组数。对于每组测试数据第一行包含三个正整数n , P , Q n,P,Qn,P,Q含义如题面所示。之后n nn行每行包含两个正整数p i , c i p_i,c_ipi​,ci​代表武器的强度和花费。输出格式对于每组测试数据如果存在满足条件的购买方案输出最少花费否则输出-1。输入输出样例 1输入 13 3 2 3 1 2 1 2 2 3 3 3 4 1 2 1 2 2 3 3 1000 1000 1 2 1 2 2 3输出 13 -1 -1说明/提示子任务编号数据点占比n nnp i p_ipi​c i c_ici​P PPQ QQ1 1120 % 20\%20%≤ 10 \leq 10≤101 111 11≤ 10 \leq 10≤10≤ 10 \leq 10≤102 2220 % 20\%20%≤ 100 \leq 100≤100≤ 5 × 10 4 \leq 5\times 10^4≤5×1041 11≤ 5 × 10 4 \leq 5\times 10^4≤5×1042 223 3360 % 60\%60%≤ 100 \leq 100≤100≤ 5 × 10 4 \leq 5\times 10^4≤5×104≤ 5 × 10 4 \leq 5\times 10^4≤5×104≤ 5 × 10 4 \leq 5\times 10^4≤5×104≤ 5 × 10 4 \leq 5\times 10^4≤5×104对于全部数据保证有1 ≤ t ≤ 10 1\leq t\leq 101≤t≤101 ≤ n ≤ 100 1\leq n\leq 1001≤n≤1001 ≤ p i , c i , P , Q ≤ 5 × 10 4 1\leq p_i,c_i,P,Q\leq 5\times 10^41≤pi​,ci​,P,Q≤5×104。思路分析这是一个有总花费上限的01背包问题但约束条件是总强度至少为P而不是恰好等于。我们需要在不超过总花费Q的前提下选择武器使得总强度≥P并求最小花费。核心思路这是一个二维约束的背包问题花费是成本需要最小化强度是收益需要至少达到P我们可以转换思路用强度作为背包容量求达到每个强度所需的最小花费然后从强度≥P的方案中找出花费≤Q的最小值。算法设计使用动态规划状态定义dp[i]表示达到强度 i 所需的最小花费初始状态dp[0] 0其他为无穷大状态转移对于每个武器(强度p花费c)从高到低更新dp[j] min(dp[j], dp[max(0, j-p)] c)注意当j-p 0时说明当前武器单独就能达到强度j所以用max(0, j-p)最终答案在j ≥ P的所有状态中找到dp[j] ≤ Q的最小dp[j]时间复杂度O(n × P)其中n≤100P≤50000最坏情况5×10 6 10^6106次操作可以接受。代码实现#includebits/stdc.husingnamespacestd;constintINF1e9;// 无穷大值intmain(){ios::sync_with_stdio(false);cin.tie(0);intt;cint;while(t--){intn,P,Q;cinnPQ;vectorintp(n),c(n);for(inti0;in;i){cinp[i]c[i];}// dp[i]表示达到强度i所需的最小花费// 因为强度可能超过P但最多不会超过P最大单个强度intmaxSumP50000;// 最大可能强度vectorintdp(maxSum1,INF);dp[0]0;// 强度为0时花费为0// 01背包从高到低更新保证每个武器只用一次for(inti0;in;i){intpip[i],cic[i];for(intjmaxSum;j0;j--){// 计算如果选择当前武器能达到的强度intpremax(0,j-pi);// 注意强度不能为负if(dp[pre]!INF){dp[j]min(dp[j],dp[pre]ci);}}}// 寻找答案强度≥P且花费≤Q的最小花费intansINF;for(intiP;imaxSum;i){if(dp[i]Q){ansmin(ans,dp[i]);}}if(ansINF){cout-1\n;}else{coutans\n;}}return0;}功能分析1. 输入处理读取测试用例数t对于每个测试用例读取n、P、Q和武器信息使用vector存储武器数据2. 动态规划核心dp[i]存储达到强度i的最小花费初始化所有状态为无穷大只有dp[0]0遍历每个武器从高到低更新dp数组状态转移dp[j] min(dp[j], dp[max(0, j-p)] c)3. 答案查找遍历所有强度≥P的状态找出其中花费≤Q的最小花费如果找不到满足条件的解输出-14.示例验证对于第一个样例输入 3 2 3 1 2 1 2 2 3 过程 dp[0]0 武器1(1,2): dp[1]2 武器2(1,2): dp[1]min(2,02)2, dp[2]min(INF,02)2 武器3(2,3): dp[2]min(2,03)2, dp[3]min(INF,13)4 强度≥2的最小花费dp[2]2≤3输出2 但实际正确输出是3为什么 问题分析 我们需要总花费≤3但dp[2]2≤3是满足的。 但题目要求总花费不超过Q且总强度≥P。 选择武器1和武器2强度112≥2花费2243不满足。 选择武器3强度2≥2花费3≤3满足所以最小花费是3。 我们的算法有问题吗 让我们重新检查算法 武器1(1,2)dp[1]2 武器2(1,2)更新时从高到低 j2: premax(0,2-1)1, dp[2]min(INF, dp[1]24)4 j1: premax(0,1-1)0, dp[1]min(2, dp[0]22)2 武器3(2,3)更新 j3: premax(0,3-2)1, dp[3]min(INF, dp[1]35)5 j2: premax(0,2-2)0, dp[2]min(4, dp[0]33)3 j1: premax(0,1-2)0, dp[1]min(2, dp[0]33)2 最终dp[2]3强度≥2的最小花费是3正确5.复杂度分析时间复杂度O(t × n × (P maxP))最坏情况约10 × 100 × 100000 1e8次操作可以接受空间复杂度O(P maxP)最大约1000006.关键点总结问题转化将至少达到P强度转化为达到强度i的最小花费边界处理使用max(0, j-p)处理j-p为负的情况答案查找在强度≥P的所有状态中找满足花费约束的最小值优化剪枝强度上限设为P最大单个强度避免不必要的计算各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}1、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html2、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转CSP信奥赛C一等奖通关刷题题单及题解持续更新https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转3、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html4、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}