广东金东建设工程公司网站,容桂网站制作值得信赖,wordpress加载视频教程,wordpress 域名授权P5858 「SWTR-3」Golden Sword 题目背景 小 E 不幸在一场战斗中失去了他的金宝剑。 题目描述 制造一把金宝剑需要 nnn 种原料#xff0c;编号为 111 到 nnn#xff0c;编号为 iii 的原料的坚固值为 aia_iai​。 炼金是很讲究放入原料的顺序的#xff0c;因此小 E 必须按…P5858 「SWTR-3」Golden Sword题目背景小 E 不幸在一场战斗中失去了他的金宝剑。题目描述制造一把金宝剑需要n nn种原料编号为1 11到n nn编号为i ii的原料的坚固值为a i a_iai​。炼金是很讲究放入原料的顺序的因此小 E 必须按照1 11到n nn的顺序依次将这些原料放入炼金锅。但是炼金锅的容量非常有限它最多只能容纳w ww个原料。所幸的是每放入一个原料之前小 E 可以从中取出一些原料数量不能超过s ss个。我们定义第i ii种原料的耐久度为放入第i ii种原料时锅内的原料总数包括正在放入的原料× a i \times\ a_i×ai​则宝剑的耐久度为所有原料的耐久度之和。小 E 当然想让他的宝剑的耐久度尽可能得大这样他就可以带着它进行更多的战斗请求出耐久度的最大值。注这里的“放入第i ii种原料时锅内的原料总数包括正在放入锅中的原料详细信息请见样例。输入格式第一行三个整数n , w , s n,w,sn,w,s。第二行n nn个整数a 1 , a 2 , … , a n a_1,a_2,\dots,a_na1​,a2​,…,an​。输出格式一行一个整数表示耐久度的最大值。输入输出样例 #1输入 #15 3 3 1 3 2 4 5输出 #140输入输出样例 #2输入 #25 3 3 1 -3 -2 4 5输出 #221输入输出样例 #3输入 #37 4 2 -5 3 -1 -4 7 -6 5输出 #317输入输出样例 #4输入 #45 3 1 -1 -3 -2 -4 -5输出 #4-15说明/提示「样例说明」对于样例 1一种可行的最优方案为首先放进原料 1此时锅内有1 11种原料耐久度为1 × a 1 1 × 1 1 1\times a_11\times 111×a1​1×11。再放进原料 2此时锅内有2 22种原料耐久度为2 × a 2 2 × 3 6 2\times a_22\times 362×a2​2×36。再放进原料 3此时锅内有3 33种原料耐久度为3 × a 3 3 × 2 6 3\times a_33\times 263×a3​3×26。取出原料 1再放进原料 4此时锅内有3 33种原料耐久度为3 × a 4 3 × 4 12 3\times a_43\times 4123×a4​3×412。取出原料 4再放进原料 5此时锅内有3 33种原料耐久度为3 × a 5 3 × 5 15 3\times a_53\times 5153×a5​3×515。最终答案为1 6 6 12 15 40 166121540166121540。对于样例 2一种可行的最优方案为放进原料 1耐久度为1 × 1 1 1\times 111×11。取出原料 1放进原料 2耐久度为1 × ( − 3 ) − 3 1\times (-3)-31×(−3)−3。放进原料 3耐久度为2 × ( − 2 ) − 4 2\times (-2)-42×(−2)−4。放进原料 4耐久度为3 × 4 12 3\times 4123×412。取出原料 2放进原料 5耐久度为3 × 5 15 3\times 5153×515。最终答案为1 ( − 3 ) ( − 4 ) 12 15 21 1(-3)(-4)1215211(−3)(−4)121521。对于样例 3一种可行的最优方案为a 1 2 a 2 2 a 3 3 a 4 4 a 5 3 a 6 4 a 7 17 a_12a_22a_33a_44a_53a_64a_717a1​2a2​2a3​3a4​4a5​3a6​4a7​17。对于样例 4一种可行的最优方案为a 1 a 2 a 3 a 4 a 5 − 15 a_1a_2a_3a_4a_5-15a1​a2​a3​a4​a5​−15。「数据范围与约定」本题使用捆绑测试。Subtask #115 pointsn ≤ 10 n\leq 10n≤10。Subtask #25 pointsn ≤ 100 n\leq 100n≤100a i ≥ 0 a_i\geq0ai​≥0。Subtask #315 pointsn ≤ 300 n\leq 300n≤300。Subtask #415 pointss w n swnswn。Subtask #55 pointsa i ≥ 0 a_i\geq 0ai​≥0。Subtask #610 pointsn ≤ 2 × 10 3 n\leq 2\times 10^3n≤2×103。Subtask #710 pointss 1 s1s1。Subtask #825 points无特殊限制。对于100 % 100\%100%的数据1 ≤ s ≤ w ≤ n ≤ 5 × 10 3 1 \leq s \leq w \leq n \leq 5\times 10^31≤s≤w≤n≤5×103∣ a i ∣ ≤ 10 9 |a_i| \leq 10^9∣ai​∣≤109。对于 Subtaski ii有∣ a i ∣ ≤ 10 i 1 |a_i|\leq 10^{i1}∣ai​∣≤10i1。「帮助/说明」本题下发大样例具体输入输出见Big Sample中的 gold01-08.in/gold01-08.out。提取码757d。文件名与 Subtask 编号一一对应。「来源」Sweet Round 03 D。idea solutionET2006。C实现#includebits/stdc.husingnamespacestd;longlongn,m,s,a[5505],dp[5505][5505];intmain(){scanf(%lld %lld %lld,n,m,s);for(longlongi1;in;i)scanf(%lld,a[i]);for(longlongi0;in;i)for(longlongj0;jm;j)dp[i][j]-1008600110086001;dp[0][0]0;for(longlongi1;in;i){for(longlongjm;j;--j){for(longlongkmin(m,js-1);kj-1;--k){dp[i][j]max(dp[i][j],dp[i-1][k]j*a[i]);}}}longlongans-1008600110086001;for(longlongi0;im;i)ansmax(ans,dp[n][i]);printf(%lld,ans);return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容