题目链接：https://www.luogu.com.cn/problem/P6040
解题思路：
设状态 (f[i]) 表示老师走到第 (i) 个人的最小花费，则：
[f[i] = min_{j in [i-x, i-1]}(f[j] + (i-j-1) imes k + d)
]
暴力的方案是 (O(n cdot x)) 时间复杂度，必然超时。
所以考虑单调队列优化，维护一个单调递增的单调队列。
比较的规则是，如果队列当中存在两个坐标 (j1, j2) 且 (j1 lt j2)，则对于任意一个 (gt j1,j2) 的 (i) 来说：
- (j1) 到 (i) 所需要的花费是 ((i-1-j1) cdot k + d)
- (j2) 到 (i) 所需要的花费是 ((i-1-j2) cdot k + d)
而两者的花费只差是 ((j2-j1) cdot k)，
也就是说，既然队列是单调递增的，则对于 (j1 lt j2) 来说，必然存在
[f[j1] + (j2-j1) imes k lt f[j2]
]
实现代码如下：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 10000010;
typedef long long ll;
int n, k, d, x, tp, a[maxn], Seed;
ll f[maxn];
deque<int> que;
inline int rnd () {
static const int MOD = 1e9;
return Seed = ( 1LL * Seed * 0x66CCFF % MOD + 20120712 ) % MOD;
}
int main() {
scanf("%d%d%d%d%d", &n, &k, &d, &x, &tp);
if (tp == 0) for (int i = 1; i <= n; i ++) scanf("%d", a+i);
else {
scanf("%d", &Seed);
for (int i = 1; i <= n; i ++) a[i] = rnd();
}
f[1] = a[1];
for (int i = 2; i <= n; i ++) {
while (!que.empty()) {
int j = que.back();
if (f[j] + (ll)(i-1-j) * d >= f[i-1]) que.pop_back();
else break;
}
que.push_back(i-1);
if (que.front() < i-x) que.pop_front();
f[i] = f[que.front()] + a[i] + k + (ll)(i - que.front() - 1) * d;
}
printf("%lld
", f[n]);
return 0;
}