当前位置：首页 > news >正文

打卡信奥刷题（2944）用C++实现信奥题 P5858 「SWTR-3」Golden Sword

news 2026/5/12 17:30:29

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

输入 #1

5 3 3 1 3 2 4 5

输出 #1

输入输出样例 #2

输入 #2

5 3 3 1 -3 -2 4 5

输出 #2

输入输出样例 #3

输入 #3

7 4 2 -5 3 -1 -4 7 -6 5

输出 #3

输入输出样例 #4

输入 #4

5 3 1 -1 -3 -2 -4 -5

输出 #4

-15

说明/提示

「样例说明」

对于样例 1，一种可行的最优方案为：
首先放进原料 1，此时锅内有1 11种原料，耐久度为1 × a 1 = 1 × 1 = 1 1\times a_1=1\times 1=11×a1=1×1=1。
再放进原料 2，此时锅内有2 22种原料，耐久度为2 × a 2 = 2 × 3 = 6 2\times a_2=2\times 3=62×a2=2×3=6。
再放进原料 3，此时锅内有3 33种原料，耐久度为3 × a 3 = 3 × 2 = 6 3\times a_3=3\times 2=63×a3=3×2=6。
取出原料 1，再放进原料 4，此时锅内有3 33种原料，耐久度为3 × a 4 = 3 × 4 = 12 3\times a_4=3\times 4=123×a4=3×4=12。
取出原料 4，再放进原料 5，此时锅内有3 33种原料，耐久度为3 × a 5 = 3 × 5 = 15 3\times a_5=3\times 5=153×a5=3×5=15。
最终答案为1 + 6 + 6 + 12 + 15 = 40 1+6+6+12+15=401+6+6+12+15=40。
对于样例 2，一种可行的最优方案为：
放进原料 1，耐久度为1 × 1 = 1 1\times 1=11×1=1。
取出原料 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 4=123×4=12。
取出原料 2，放进原料 5，耐久度为3 × 5 = 15 3\times 5=153×5=15。
最终答案为1 + ( − 3 ) + ( − 4 ) + 12 + 15 = 21 1+(-3)+(-4)+12+15=211+(−3)+(−4)+12+15=21。
对于样例 3，一种可行的最优方案为：
a 1 + 2 a 2 + 2 a 3 + 3 a 4 + 4 a 5 + 3 a 6 + 4 a 7 = 17 a_1+2a_2+2a_3+3a_4+4a_5+3a_6+4a_7=17a1+2a2+2a3+3a4+4a5+3a6+4a7=17。
对于样例 4，一种可行的最优方案为：
a 1 + a 2 + a 3 + a 4 + a 5 = − 15 a_1+a_2+a_3+a_4+a_5=-15a1+a2+a3+a4+a5=−15。

「数据范围与约定」

本题使用捆绑测试。

Subtask #1（15 points）：n ≤ 10 n\leq 10n≤10。
Subtask #2（5 points）：n ≤ 100 n\leq 100n≤100，a i ≥ 0 a_i\geq0ai≥0。
Subtask #3（15 points）：n ≤ 300 n\leq 300n≤300。
Subtask #4（15 points）：s = w = n s=w=ns=w=n。
Subtask #5（5 points）：a i ≥ 0 a_i\geq 0ai≥0。
Subtask #6（10 points）：n ≤ 2 × 10 3 n\leq 2\times 10^3n≤2×103。
Subtask #7（10 points）：s = 1 s=1s=1。
Subtask #8（25 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^{i+1}∣ai∣≤10i+1。

「帮助/说明」

本题下发大样例，具体输入输出见Big Sample中的 gold01-08.in/gold01-08.out。提取码：757d。
文件名与 Subtask 编号一一对应。

「来源」

Sweet Round 03 D。
idea & solution：ET2006。

C++实现

#include<bits/stdc++.h>usingnamespacestd;longlongn,m,s,a[5505],dp[5505][5505];intmain(){scanf("%lld %lld %lld",&n,&m,&s);for(longlongi=1;i<=n;++i)scanf("%lld",&a[i]);for(longlongi=0;i<=n;++i)for(longlongj=0;j<=m;++j)dp[i][j]=-1008600110086001;dp[0][0]=0;for(longlongi=1;i<=n;++i){for(longlongj=m;j;--j){for(longlongk=min(m,j+s-1);k>=j-1;--k){dp[i][j]=max(dp[i][j],dp[i-1][k]+j*a[i]);}}}longlongans=-1008600110086001;for(longlongi=0;i<=m;++i)ans=max(ans,dp[n][i]);printf("%lld",ans);return0;}