洛谷P5858 「SWTR-03」Golden Sword
题目背景
小 E 不幸在一场战斗中失去了他的金宝剑。
题目描述
制造一把金宝剑需要 \(n\) 种原料，编号为 \(1\) 到 \(n\)，编号为 \(i\) 的原料的坚固值为 \(a_i\)。
炼金是很讲究放入原料的顺序的，因此小 E 必须按照 \(1\) 到 \(n\) 的顺序依次将这些原料放入炼金锅。
但是，炼金锅的容量非常有限，它最多只能容纳 \(w\) 个原料。
所幸的是，每放入一个原料之前，小 E 可以从中取出一些原料，数量不能超过 \(s\) 个。
- 我们定义第 \(i\) 种原料的耐久度为：放入第 \(i\) 种原料时锅内的原料总数（包括正在放入的原料） \(\times\ a_i\)，则宝剑的耐久度为所有原料的耐久度之和。
小 E 当然想让他的宝剑的耐久度尽可能得大，这样他就可以带着它进行更多的战斗，请求出耐久度的最大值。
注：这里的“放入第 \(i\) 种原料时锅内的原料总数包括正在放入锅中的原料，详细信息请见样例。
输入格式
第一行，三个整数 \(n,w,s\)。
第二行，\(n\) 个整数 \(a_1,a_2,\dots,a_n\)。
输出格式
一行一个整数，表示耐久度的最大值。
样例 #1
样例输入 #1
5 3 3
1 3 2 4 5
样例输出 #1
40
样例 #2
样例输入 #2
5 3 3
1 -3 -2 4 5
样例输出 #2
21
样例 #3
样例输入 #3
7 4 2
-5 3 -1 -4 7 -6 5
样例输出 #3
17
样例 #4
样例输入 #4
5 3 1
-1 -3 -2 -4 -5
样例输出 #4
-15
提示
「样例说明」
- 对于样例 1，一种可行的最优方案为：
首先放进原料 1，此时锅内有 \(1\) 种原料，耐久度为 \(1\times a_1=1\times 1=1\)。
再放进原料 2，此时锅内有 \(2\) 种原料，耐久度为 \(2\times a_2=2\times 3=6\)。
再放进原料 3，此时锅内有 \(3\) 种原料，耐久度为 \(3\times a_3=3\times 2=6\)。
取出原料 1，再放进原料 4，此时锅内有 \(3\) 种原料，耐久度为 \(3\times a_4=3\times 4=12\)。
取出原料 4，再放进原料 5，此时锅内有 \(3\) 种原料，耐久度为 \(3\times a_5=3\times 5=15\)。
最终答案为 \(1+6+6+12+15=40\)。 - 对于样例 2，一种可行的最优方案为：
放进原料 1，耐久度为 \(1\times 1=1\)。
取出原料 1，放进原料 2，耐久度为 \(1\times (-3)=-3\)。
放进原料 3，耐久度为 \(2\times (-2)=-4\)。
放进原料 4，耐久度为 \(3\times 4=12\)。
取出原料 2，放进原料 5，耐久度为 \(3\times 5=15\)。
最终答案为 \(1+(-3)+(-4)+12+15=21\)。 - 对于样例 3，一种可行的最优方案为：
\(a_1+2a_2+2a_3+3a_4+4a_5+3a_6+4a_7=17\)。 - 对于样例 4，一种可行的最优方案为：
\(a_1+a_2+a_3+a_4+a_5=-15\)。
「数据范围与约定」
本题使用捆绑测试。
- Subtask #1（15 points）：\(n\leq 10\)。
- Subtask #2（5 points）：\(n\leq 100\)，\(a_i\geq0\)。
- Subtask #3（15 points）：\(n\leq 300\)。
- Subtask #4（15 points）：\(s=w=n\)。
- Subtask #5（5 points）：\(a_i\geq 0\)。
- Subtask #6（10 points）：\(n\leq 2\times 10^3\)。
- Subtask #7（10 points）：\(s=1\)。
- Subtask #8（25 points）：无特殊限制。
对于 \(100\%\) 的数据，\(1 \leq s \leq w \leq n \leq 5\times 10^3\)，\(|a_i| \leq 10^9\)。对于 Subtask \(i\) 有 \(|a_i|\leq 10^{i+1}\)。
「帮助/说明」
本题下发大样例，具体输入输出见 Big Sample 中的 gold01-08.in/gold01-08.out。提取码：757d。
文件名与 Subtask 编号一一对应。
「来源」
Sweet Round 03 D。
idea & solution：ET2006。
解题思路
状态表示：\(f[i][j]\) 表示考虑前 \(i\) 个原料中的某些放入且总数为 \(j\) 的耐久度集合，要求的是其最大值。
状态计算：题目提到，每次放入原料之前，可以取出不超过 \(s\) 个原料，当前有 \(j-1\)，那么我们枚举取出的若干原料前已有的原料个数 \(k\)，明显 \(j-1≤k≤j+s-1\)，可以取走 \(0-s\) 个，但一定要放入一个。那么 \(f[i][j]=max(f[i-1][k])+a[i]*j\)。这样的时间复杂度为 \(O(nws)\)，会超时，但是我们发现了 \(max(f[i-1][k])\)，求一个区间的最大值，并且这个区间是已知的，我们可以使用单调队列优化。
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 5010, M = 20010;
typedef pair<int, int> PII;
typedef long long LL;
int n, w, s;
LL a[N], f[N][N], pos[N], q[N]; // 选择前i个原料中的某些放入且总数为j的耐久度集合
int main ()
{
scanf("%d%d%d", &n, &w, &s);
for(int i = 1; i <= n; i ++)
scanf("%lld", &a[i]);
memset(f, 0x80, sizeof f);
f[0][0] = 0;
for(int i = 1; i <= n; i ++)
{
int hh = 0, tt = -1;
q[++ tt] = f[i - 1][w];
pos[hh] = w;
for(int j = w; j; j --)
{
// for(int k = j - 1; k <= min(w, j + s - 1); k ++)
// f[i][j] = max(f[i][j], f[i - 1][k] + a[i] * j);
while(hh <= tt && j + s - 1 < pos[hh]) hh ++;
while(hh <= tt && q[tt] < f[i - 1][j - 1]) tt --;
pos[++ tt] = j - 1;
q[tt] = f[i - 1][j - 1];
f[i][j] = q[hh] + j * a[i];
}
}
LL ans = 0x8080808080808080;
for(int j = 1; j <= w; j ++)
ans = max(ans, f[n][j]);
printf("%lld\n", ans);
return 0;
}