知识点: 线性DP，单调队列
原题面
题目要求:
给定 \(n\) 个物品，编号为 \(a_1\sim a_n\)。
现需要将其按顺序放到容量为 \(w\) 的箱子里。
每放入一个物品前，可以从箱子中取出 \(s\) 个物品。
定义 第 \(i\) 个物品的价值为，将其放入箱子后，箱中物品数 \(\times a_i\)，求最大价值和。
\(1\le s\le w\le n \le 5.5\times 10^3, 0\le \mid a\mid \le 10^9\)
分析题意
算法一
发现一些奇妙性质。
- 已经放入箱子的物品本质相同，对之后放入物品的贡献都为 \(1\)。
- 欲使加入新物品后，箱子内物品数为 \(j\)，可在物品数为 \(j-1\) 直接加入，或删去 \(\le s\) 个物品。
但两种方法对答案的贡献等价。
则有非常显然的做法。
设 \(f_{i,j}\) 表示，放到第 \(i\) 个物品，箱子里有 \(j\) 个元素的最大价值和。
\[f_{i,j} = \max_{k=j-1}^{\min\{j+s-1,w\}} \{ f_{i-1,k} \} + j\times a_i
\]
转移时只与 \(i-1\) 有关，则 \(i\) 维可以滚动数组滚掉，保证空间复杂度。
需每次都将 \(f_{now}\) 初始化为负无穷。
注意循环边界的细节。
for (int i = 1; i <= n; ++ i, now ^= 1) {
memset(f[now], 128, sizeof(f[now]));
for (int j = 1; j <= min(i, w); ++ j) {
for (int k = j - 1; k <= min(i, min(j + s - 1, w)); ++ k) {
f[now][j] = max(f[now][j], f[now ^ 1][k] + (ll) j * a[i]);
}
}
}
时间复杂度上限 \(O(n^3)\)，在 \(s=w=n\) 时复杂度最高。
在随机数据下能骗到 \(\text{85pts}\)。
算法二
被 \(\text{Subtask 4}\) 卡掉了咋办啊？
观察代码：
for (int j = 1; j <= min(i, w); ++ j)
for (int k = j - 1; k <= min(i, min(j + s - 1, w)); ++ k)
发现 \(k\) 的范围区间，随 \(j\) 的增加，单调右移，考虑单调队列优化。
优化掉一重循环，省去了枚举 \(k\) 的复杂度。
复杂度 \(O(n^2)\)，期望得分 \(\text{100pts}\)
代码实现
//
/*
By:Luckyblock
*/
#include <cstdio>
#include <ctype.h>
#include <cstring>
#include <algorithm>
#define ll long long
#define min std::min
#define max std::max
const int kMaxn = 5510;
//=============================================================
int n, w, s, now, limit, head, tail, k;
ll ans, a[kMaxn], f[2][kMaxn], q[kMaxn];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
int Query(int val) {
while (q[head] < val - 1 && head <= tail) head ++;
return q[head];
}
void Insert(int val) {
while (f[now ^ 1][q[tail]] <= f[now ^ 1][val] && head <= tail) tail --;
q[++ tail] = val;
}
//=============================================================
int main() {
n = read(), w = read(), s = read();
for (int i = 1; i <= n; ++ i) a[i] = (ll) read();
for (int i = 1; i <= n; ++ i, now ^= 1) {
memset(f[now], 128, sizeof(f[now]));
head = 1, tail = k = 0, limit = min(i, w);
for (int j = 1; j <= limit; ++ j) {
while (k < min(j + s - 1, limit)) Insert(++ k);
f[now][j] = max(f[now][j], f[now ^ 1][Query(j)] + (ll) j * a[i]);
}
}
ans = f[now][0];
for (int i = 1; i <= w; ++ i) ans = max(ans, f[now ^ 1][i]);
printf("%lld\n", ans);
return 0;
}