2026年山东省【信息学体验营】复赛真题及题解T5精选矿石题目描述你驾驶宇宙飞船在星际探险中降落到了一颗小行星上发现了一堆富矿。经过初步检测这里共有n nn块非常珍贵的矿石每块矿石都有一定的重量w i w_iwi和能量价值v i v_ivi。令人惊奇的是这些矿石的重量非常接近最轻的和最重的矿石重量相差不超过10 1010。已知你的飞船货舱总载重量上限为m mm你想在不超过货舱载重的前提下选取一些矿石带回地球每块矿石最多只能搬运一次使得所选矿石的总能量价值最大请输出这个最大值。输入格式第一行两个整数n , m n,mn,m含义如上。接下来n nn行每行两个整数w i , v i w_i,v_iwi,vi分别表示第i ii块矿石的重量和能量价值。输出格式一个整数表示能获得的最大总能量价值。如果一块矿石都装不了即每块矿石的重量都大于m mm输出0 00。输入输出样例 1输入 14 6 2 1 3 4 4 10 3 8输出 112输入输出样例 2输入 24 1000000000 500000002 10 499999997 8 499999996 2 500000004 15输出 218说明/提示【样例1 11解释】最优方案选择矿石2 22重3 33价值4 44和矿石4 44重3 33价值8 88总重6 66总价值12 1212。【数据范围】1 ≤ n ≤ 100 1\le n\le 1001≤n≤1001 ≤ m ≤ 10 9 1\le m\le 10^91≤m≤1091 ≤ w i ≤ 10 9 1\le w_i\le 10^91≤wi≤1091 ≤ v i ≤ 10 7 1\le v_i\le 10^71≤vi≤107。所有输入为整数。测试点编号n nnm mm特殊性质1 ∼ 5 1\sim 51∼5≤ 20 \le 20≤201 ≤ m ≤ 100 1\le m\le 1001≤m≤100A \mathrm{A}A6 ∼ 14 6\sim 146∼14≤ 100 \le 100≤1001 ≤ m ≤ 10 5 1\le m\le 10^51≤m≤105无15 ∼ 20 15\sim 2015∼20≤ 100 \le 100≤1001 ≤ m ≤ 10 9 1\le m\le 10^91≤m≤109无性质A \mathrm{A}A( ∑ 1 ≤ i ≤ n w i ≤ m w i ) ≤ m \displaystyle\left(\sum_{\substack{1\le i\le n\\w_i\le m}}w_i\right)\le m1≤i≤nwi≤m∑wi≤m即重量小于等于m mm的矿石的重量和不超过m mm。思路分析这是一道0/1 背包问题但背包容量 m 可达10 9 10^9109不能按重量直接 DP。关键性质所有矿石重量相差不超过 10。设最轻重量为base则每块矿石重量可写成w i b a s e d i , 0 ≤ d i ≤ 10 w_i base d_i, \quad 0 \le d_i \le 10wibasedi,0≤di≤10如果选了 (k) 块总重量为k × b a s e ∑ d i k \times base \sum d_ik×base∑di其中偏移总和∑ d i ≤ 10 × n 1000 \sum d_i \le 10 \times n 1000∑di≤10×n1000因为n ≤ 100 n \le 100n≤100。因此我们可以用三维 DP 枚举选了几块和偏移总和状态dp[i][j][s]表示考虑前i块矿石恰好选了j块偏移总和为s时的最大总价值。转移不选第i块dp[i][j][s] max(dp[i][j][s], dp[i-1][j][s])选第i块偏移为d价值为vdp[i][j][s] max(dp[i][j][s], dp[i-1][j-1][s-d] v)初始化dp[0][0][0] 0其余为负无穷。最终答案枚举j和s若j * base s ≤ m则用dp[n][j][s]更新答案。复杂度时间O ( n × n × 10 n ) O ( 10 n 3 ) O(n \times n \times 10n) O(10n^3)O(n×n×10n)O(10n3)(n100) 时约10 7 10^7107可行。空间O ( n 2 ⋅ 10 n ) O(n^2 \cdot 10n)O(n2⋅10n)约为101 × 101 × 1001 101 \times 101 \times 1001101×101×1001个int约 40 MB可接受。数据类型重量相关w i w_iwi,m,base,baseWeight,remain可能超过int最大约10 11 10^{11}1011故使用long long。价值总和最大为100 × 10 7 10 9 100 \times 10^7 10^9100×107109在int范围内所以dp数组和答案用int即可。代码实现#includebits/stdc.husingnamespacestd;constintNEG-1e9;// 负无穷价值不会低于0所以用-1e9足够intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn;longlongm;cinnm;vectorlonglongw(n);vectorintv(n);longlongbaseLLONG_MAX;for(inti0;in;i){cinw[i]v[i];basemin(base,w[i]);}// 最轻的矿石都装不下一块都选不了if(basem){cout0\n;return0;}// 计算每块矿石的偏移量 d_i (0 ~ 10)vectorintd(n);for(inti0;in;i){d[i](int)(w[i]-base);}intmaxExtra10*n;// 偏移总和最大可能值// dp[i][j][s]前 i 块选 j 块偏移总和为 s 的最大价值// 使用 int 即可总价值 ≤ 1e9vectorvectorvectorintdp(n1,vectorvectorint(n1,vectorint(maxExtra1,NEG)));dp[0][0][0]0;for(inti1;in;i){intcurDd[i-1];intcurVv[i-1];for(intj0;ji;j){for(ints0;smaxExtra;s){// 不选第 i 块if(dp[i-1][j][s]!NEG){dp[i][j][s]max(dp[i][j][s],dp[i-1][j][s]);}// 选第 i 块if(j1scurDdp[i-1][j-1][s-curD]!NEG){dp[i][j][s]max(dp[i][j][s],dp[i-1][j-1][s-curD]curV);}}}}intans0;// 最大价值int 足够// 枚举选了多少块和偏移总和检查是否满足容量for(intj0;jn;j){longlongbaseWeight1LL*j*base;// 基础总重量if(baseWeightm)continue;longlongremainm-baseWeight;if(remainmaxExtra)remainmaxExtra;// 偏移总和不能超过上限for(ints0;s(int)remain;s){if(dp[n][j][s]!NEG){ansmax(ans,dp[n][j][s]);}}}coutans\n;return0;}更多内容请关注专栏信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转3、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.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解信奥赛C普及组CSP-J一等奖通关刷题题单及题解https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、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.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;} 2026年山东省【信息学体验营】复赛真题及题解T5：精选矿石
2026年山东省【信息学体验营】复赛真题及题解T5精选矿石题目描述你驾驶宇宙飞船在星际探险中降落到了一颗小行星上发现了一堆富矿。经过初步检测这里共有n nn块非常珍贵的矿石每块矿石都有一定的重量w i w_iwi和能量价值v i v_ivi。令人惊奇的是这些矿石的重量非常接近最轻的和最重的矿石重量相差不超过10 1010。已知你的飞船货舱总载重量上限为m mm你想在不超过货舱载重的前提下选取一些矿石带回地球每块矿石最多只能搬运一次使得所选矿石的总能量价值最大请输出这个最大值。输入格式第一行两个整数n , m n,mn,m含义如上。接下来n nn行每行两个整数w i , v i w_i,v_iwi,vi分别表示第i ii块矿石的重量和能量价值。输出格式一个整数表示能获得的最大总能量价值。如果一块矿石都装不了即每块矿石的重量都大于m mm输出0 00。输入输出样例 1输入 14 6 2 1 3 4 4 10 3 8输出 112输入输出样例 2输入 24 1000000000 500000002 10 499999997 8 499999996 2 500000004 15输出 218说明/提示【样例1 11解释】最优方案选择矿石2 22重3 33价值4 44和矿石4 44重3 33价值8 88总重6 66总价值12 1212。【数据范围】1 ≤ n ≤ 100 1\le n\le 1001≤n≤1001 ≤ m ≤ 10 9 1\le m\le 10^91≤m≤1091 ≤ w i ≤ 10 9 1\le w_i\le 10^91≤wi≤1091 ≤ v i ≤ 10 7 1\le v_i\le 10^71≤vi≤107。所有输入为整数。测试点编号n nnm mm特殊性质1 ∼ 5 1\sim 51∼5≤ 20 \le 20≤201 ≤ m ≤ 100 1\le m\le 1001≤m≤100A \mathrm{A}A6 ∼ 14 6\sim 146∼14≤ 100 \le 100≤1001 ≤ m ≤ 10 5 1\le m\le 10^51≤m≤105无15 ∼ 20 15\sim 2015∼20≤ 100 \le 100≤1001 ≤ m ≤ 10 9 1\le m\le 10^91≤m≤109无性质A \mathrm{A}A( ∑ 1 ≤ i ≤ n w i ≤ m w i ) ≤ m \displaystyle\left(\sum_{\substack{1\le i\le n\\w_i\le m}}w_i\right)\le m1≤i≤nwi≤m∑wi≤m即重量小于等于m mm的矿石的重量和不超过m mm。思路分析这是一道0/1 背包问题但背包容量 m 可达10 9 10^9109不能按重量直接 DP。关键性质所有矿石重量相差不超过 10。设最轻重量为base则每块矿石重量可写成w i b a s e d i , 0 ≤ d i ≤ 10 w_i base d_i, \quad 0 \le d_i \le 10wibasedi,0≤di≤10如果选了 (k) 块总重量为k × b a s e ∑ d i k \times base \sum d_ik×base∑di其中偏移总和∑ d i ≤ 10 × n 1000 \sum d_i \le 10 \times n 1000∑di≤10×n1000因为n ≤ 100 n \le 100n≤100。因此我们可以用三维 DP 枚举选了几块和偏移总和状态dp[i][j][s]表示考虑前i块矿石恰好选了j块偏移总和为s时的最大总价值。转移不选第i块dp[i][j][s] max(dp[i][j][s], dp[i-1][j][s])选第i块偏移为d价值为vdp[i][j][s] max(dp[i][j][s], dp[i-1][j-1][s-d] v)初始化dp[0][0][0] 0其余为负无穷。最终答案枚举j和s若j * base s ≤ m则用dp[n][j][s]更新答案。复杂度时间O ( n × n × 10 n ) O ( 10 n 3 ) O(n \times n \times 10n) O(10n^3)O(n×n×10n)O(10n3)(n100) 时约10 7 10^7107可行。空间O ( n 2 ⋅ 10 n ) O(n^2 \cdot 10n)O(n2⋅10n)约为101 × 101 × 1001 101 \times 101 \times 1001101×101×1001个int约 40 MB可接受。数据类型重量相关w i w_iwi,m,base,baseWeight,remain可能超过int最大约10 11 10^{11}1011故使用long long。价值总和最大为100 × 10 7 10 9 100 \times 10^7 10^9100×107109在int范围内所以dp数组和答案用int即可。代码实现#includebits/stdc.husingnamespacestd;constintNEG-1e9;// 负无穷价值不会低于0所以用-1e9足够intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn;longlongm;cinnm;vectorlonglongw(n);vectorintv(n);longlongbaseLLONG_MAX;for(inti0;in;i){cinw[i]v[i];basemin(base,w[i]);}// 最轻的矿石都装不下一块都选不了if(basem){cout0\n;return0;}// 计算每块矿石的偏移量 d_i (0 ~ 10)vectorintd(n);for(inti0;in;i){d[i](int)(w[i]-base);}intmaxExtra10*n;// 偏移总和最大可能值// dp[i][j][s]前 i 块选 j 块偏移总和为 s 的最大价值// 使用 int 即可总价值 ≤ 1e9vectorvectorvectorintdp(n1,vectorvectorint(n1,vectorint(maxExtra1,NEG)));dp[0][0][0]0;for(inti1;in;i){intcurDd[i-1];intcurVv[i-1];for(intj0;ji;j){for(ints0;smaxExtra;s){// 不选第 i 块if(dp[i-1][j][s]!NEG){dp[i][j][s]max(dp[i][j][s],dp[i-1][j][s]);}// 选第 i 块if(j1scurDdp[i-1][j-1][s-curD]!NEG){dp[i][j][s]max(dp[i][j][s],dp[i-1][j-1][s-curD]curV);}}}}intans0;// 最大价值int 足够// 枚举选了多少块和偏移总和检查是否满足容量for(intj0;jn;j){longlongbaseWeight1LL*j*base;// 基础总重量if(baseWeightm)continue;longlongremainm-baseWeight;if(remainmaxExtra)remainmaxExtra;// 偏移总和不能超过上限for(ints0;s(int)remain;s){if(dp[n][j][s]!NEG){ansmax(ans,dp[n][j][s]);}}}coutans\n;return0;}更多内容请关注专栏信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转3、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.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解信奥赛C普及组CSP-J一等奖通关刷题题单及题解https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、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.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}