简单题，但是我在 DP 状态设计上卡了一会儿，显然是练得不够。
设 $f_i$ 表示运走前 $i$ 个单位时间来的人，最小的等待时间是多少。
容易得到转移方程：
$$f_i = \min\limits_{j=0}^{i-m} \{ f_j + \sum\limits_{j \lt t_k \leq i} (i - t_k) \}$$
前缀和优化一下，记 $s$ 为 $t$ 的前缀和，$c$ 为 $[0,i]$ 时间内来了多少人。
$$f_i = \min\limits_{j=0}^{i-m} \{ f_j + (c_i - c_j) \times i - (s_i - s_j) \}$$
顺便提一下当时第一想法是通过 $i,j$ 二分出 $t$ 序列合法的 $l,r$，但显然由于 $t$ 足够小可以直接在上面做前缀和。
//O(T^2) DP
//注意车可能晚到，所以往后延伸 m 个单位时间
#include <bits/stdc++.h>
using namespace std;
const int N = 515, M = N + 4e6 + 15;
int n, m, Max = 0;
int t[N], c[M];
long long s[M], dp[M];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &t[i]), Max = max(Max, t[i]);
c[t[i]]++, s[t[i]] += t[i];
}
for (int i = 1; i <= Max + m; i++) c[i] += c[i - 1], s[i] += s[i - 1];
memset(dp, 0x3f, sizeof dp);
for (int i = 0; i <= Max + m; i++) {
dp[i] = i * 1ll * c[i] - s[i];
for (int j = 0; j <= i - m; j++)
dp[i] = min(dp[i], dp[j] + (c[i] - c[j]) * 1ll * i - (s[i] - s[j]));
}
long long ans = 1e18;
for (int i = Max; i <= Max + m; i++) ans = min(ans, dp[i]);
printf("%d\n", ans);
return 0;
}
然后可以减少无用转移：发现 $\geq 2m$ 的段分成两部分 $m$ 一定不劣，所以减小转移范围。
//O(Tm) DP
//注意车可能晚到，所以往后延伸 m 个单位时间
//然后可以把 >=2m 的分成两部分，减少无用转移，这样一定不劣
#include <bits/stdc++.h>
using namespace std;
const int N = 515, M = N + 4e6 + 15;
int n, m, Max = 0;
int t[N], c[M];
long long s[M], dp[M];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &t[i]), Max = max(Max, t[i]);
c[t[i]]++, s[t[i]] += t[i];
}
for (int i = 1; i <= Max + m; i++) c[i] += c[i - 1], s[i] += s[i - 1];
memset(dp, 0x3f, sizeof dp);
for (int i = 0; i <= Max + m; i++) {
dp[i] = i * 1ll * c[i] - s[i];
for (int j = max(0, i - 2 * m + 1); j <= i - m; j++)
dp[i] = min(dp[i], dp[j] + (c[i] - c[j]) * 1ll * i - (s[i] - s[j]));
}
long long ans = 1e18;
for (int i = Max; i <= Max + m; i++) ans = min(ans, dp[i]);
printf("%d\n", ans);
return 0;
}
这样已经可以在洛谷上通过了，但是 acw 会卡。
那么把式子再抄一遍：
$$f_i = \min\limits_{j=0}^{i-m} \{ f_j + (c_i - c_j) \times i - (s_i - s_j) \}$$
观察上面的式子，乘积形式已经出来了，那么展开后，照常推式子。
结果是：
$$\frac{(f_{j_1} + s_{j_1}) - (f_{j_2} + s_{j_2})}{c_{j_1} - c_{j_2}} \geq i$$
这玩意儿的 $k=i$ 是单增的，$x=c_j$ 也是单增的，所以可以直接单调队列队头转移。
//O(m) DP
//注意车可能晚到，所以往后延伸 m 个单位时间
//然后可以把 >=2m 的分成两部分，减少无用转移，这样一定不劣
//推一下斜率优化就好了。
#include <bits/stdc++.h>
using namespace std;
const int N = 515, M = N + 4e6 + 15;
int n, m, Max = 0;
int t[N], c[M];
long long s[M], dp[M];
long long X(int p) { return c[p]; }
long long Y(int p) { return dp[p] + s[p]; }
double slope(int a, int b) {
if (X(a) == X(b)) {
if (Y(a) == Y(b)) return 0;
if (Y(a) < Y(b)) return 1e18;
return -1e18;
}
return (Y(a) - Y(b)) * 1.00 / (X(a) - X(b));
}
int q[M], st, ed;
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &t[i]), Max = max(Max, t[i]);
c[t[i]]++, s[t[i]] += t[i];
}
for (int i = 1; i <= Max + m; i++) c[i] += c[i - 1], s[i] += s[i - 1];
memset(dp, 0x3f, sizeof dp);
for (int i = 0; i < m; i++) dp[i] = i * 1ll * c[i] - s[i];
st = ed = 1, q[1] = 0;
for (int i = m; i <= Max + m; i++) {
dp[i] = i * 1ll * c[i] - s[i];
while (st < ed && slope(q[st], q[st + 1]) <= i) st++;
int j = q[st];
dp[i] = min(dp[i], dp[j] + (c[i] - c[j]) * 1ll * i - (s[i] - s[j]));
while (st < ed && slope(q[ed - 1], q[ed]) >= slope(q[ed], i - m + 1)) ed--;
q[++ed] = i - m + 1;
}
long long ans = 1e18;
for (int i = Max; i <= Max + m; i++) ans = min(ans, dp[i]);
printf("%d\n", ans);
return 0;
}
