企业官网建设流程全解析

如何迁移wordpress网站,长春做网站设计,官网网页制作,青海风控平台安卓版2025年6月GESP真题及题解(C七级): 调味平衡 题目描述 小 A 准备了 nnn 种食材用来制作料理#xff0c;这些食材依次以 1,2,…,n1,2,\dots,n1,2,…,n 编号#xff0c;第 iii 种食材的酸度为 aia_iai​#xff0c;甜度为 bib_ibi​。对于每种食材#xff0c;小 A 可以选择将…2025年6月GESP真题及题解(C七级): 调味平衡题目描述小 A 准备了n nn种食材用来制作料理这些食材依次以1 , 2 , … , n 1,2,\dots,n1,2,…,n编号第i ii种食材的酸度为a i a_iai​甜度为b i b_ibi​。对于每种食材小 A 可以选择将其放入料理或者不放入料理。料理的酸度A AA为放入食材的酸度之和甜度B BB为放入食材的甜度之和。如果料理的酸度和甜度相等那么料理的调味是平衡的。过于清淡的料理并不好吃因此小 A 想在满足料理调味平衡的前提下合理选择食材最大化料理的酸度与甜度之和。你能帮他求出在调味平衡的前提下料理酸度与甜度之和的最大值吗输入格式第一行一个正整数n nn表示食材种类数量。接下来n nn行每行两个正整数a i , b i a_i,b_iai​,bi​表示食材的酸度和甜度。输出格式输出共一行一个整数表示在调味平衡的前提下料理酸度与甜度之和的最大值。输入输出样例 1输入 13 1 2 2 4 3 2输出 18输入输出样例 2输入 25 1 1 2 3 6 1 8 2 5 7输出 22说明/提示对于40 % 40\%40%的测试点保证1 ≤ n ≤ 10 1 \le n \le 101≤n≤101 ≤ a i , b i ≤ 10 1 \le a_i,b_i \le 101≤ai​,bi​≤10。对于另外20 % 20\%20%的测试点保证1 ≤ n ≤ 50 1 \le n \le 501≤n≤501 ≤ a i , b i ≤ 10 1 \le a_i,b_i \le 101≤ai​,bi​≤10。对于所有测试点保证1 ≤ n ≤ 100 1 \le n \le 1001≤n≤1001 ≤ a i , b i ≤ 500 1 \le a_i,b_i \le 5001≤ai​,bi​≤500。核心思路这道题可以转化为一个动态规划问题我们需要选择若干食材使得酸度之和与甜度之和相等即差值之和为0并最大化酸度与甜度之和即所有选中的食材的a i b i a_ib_iai​bi​之和。1.问题转换每个食材有酸度a i a_iai​和甜度b i b_ibi​定义差值d i a i − b i d_i a_i - b_idi​ai​−bi​价值v i a i b i v_i a_i b_ivi​ai​bi​。我们需要选择一个子集使得 sum(d i d_idi​) 0并最大化sum(v i v_ivi​)。2.动态规划设计由于d i d_idi​可能为负总差值范围在[-50000, 50000]之间n ≤ 100,∣ d i ∣ |d_i|∣di​∣≤ 500使用偏移量offset 50000将负数下标转化为非负数。定义dp[j]表示当前考虑过的食材中总差值偏移后为j时的最大总价值。初始状态dp[offset] 0其余为负无穷。对于每个食材d i d_idi​≠ 0若d i d_idi​ 0则j从大到小更新防止重复选择。若d i d_idi​ 0则j从小到大更新同样防止重复选择。对于d i d_idi​ 0的食材直接将其价值累加到基础值中因为选择它们不会影响差值且总是优选的。3.最终答案最终dp[offset]即为满足平衡条件时的最大总价值。4.复杂度分析时间复杂度O(n × range)其中 range 100001约为10 7 10^7107在题目限制内可行。空间复杂度O(range)使用一维数组优化。代码实现#includebits/stdc.husingnamespacestd;constintoffset50000;// 差值偏移量使负数下标可表示constintrange100001;// 差值范围 [-50000, 50000] - [0, 100000]constintINF-1e9;// 负无穷表示不可达状态intmain(){intn;cinn;intbase0;// 基础价值所有 d_i0 的食材价值之和vectorpairint,intitems;// 存放 d_i ≠ 0 的食材 (d_i, v_i)for(inti0;in;i){inta,b;cinab;intda-b;intvab;if(d0){basev;// d0 的食材直接加入基础价值}else{items.push_back({d,v});}}// dp[j] 表示总差值偏移后为 j 时的最大总价值vectorintdp(range,INF);dp[offset]base;// 初始状态不选任何非零食材差值为0价值为base// 动态规划处理每个非零食材for(auto[d,v]:items){if(d0){// 正差值逆序遍历避免重复选择for(intjrange-1;j0;j--){if(dp[j]!INFjdrange){dp[jd]max(dp[jd],dp[j]v);}}}else{// 负差值正序遍历避免重复选择for(intj0;jrange;j){if(dp[j]!INFjd0){dp[jd]max(dp[jd],dp[j]v);}}}}// 最终差值为0即偏移后为offset的最大价值即为答案coutdp[offset]endl;return0;}功能分析1.输入处理读取食材数量n和每个食材的酸度、甜度。计算每个食材的差值d_i和价值v_i。将d_i 0的食材价值累加到base中其余存入items列表。2.动态规划初始化dp数组初始化为负无穷表示不可达状态。dp[offset]初始化为base代表不选任何非零食材时的基础状态。3.状态转移对每个非零食材根据其差值正负决定遍历方向确保每个食材只被考虑一次0-1背包。转移方程dp[新差值] max(dp[新差值], dp[原差值] v i v_ivi​)。4.输出结果最终dp[offset]即为满足平衡条件的最大总价值。5.示例验证样例1输入 3 1 2 2 4 3 2 处理 食材1: d-1, v3 食材2: d-2, v6 食材3: d1, v5 动态规划后dp[offset]8输出8。样例2输入 5 1 1 2 3 6 1 8 2 5 7 处理 食材1: d0, v2 - base2 食材2: d-1, v5 食材3: d5, v7 食材4: d6, v10 食材5: d-2, v12 动态规划后dp[offset]2输出2。各种学习资料助力大家一站式学习和提升#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;}