有 $n$ 个站台，从左往右编号为 $1, 2, \cdots, n$，每个站台初始时 ($0$ 时刻) 有 $a_i$ 个人。
每个时刻，会依次发生如下事件：
你可以选择召唤一辆向右行驶的火车 (最大载客量为 $K$)，接走所有站台上从左往右数的前 $K$ 个人。
如果所有站台上的总人数不足 $K$，则接走所有站台上的人。
这个过程你可以执行任意多次 (即在同一时刻可以召唤任意辆火车)。
在该时刻末，第 $i$ 个站台上会增加 $b_i$ (只与站台编号有关的常数) 个人。
如果第 $i$ 个站台上的人数超过 $c_i$，则认为你输了。
你现在要坚持 $t$ 时刻，求你在不输的前提下，至少需要召唤多少辆火车。
第一行包含三个正整数 $n, t, k$ ($n, t \leq 200; k \leq 10^9$)，表示站台的个数，你需要坚持的时间以及每辆火车的载客量。
接下来的 $n$ 行，每行包含三个非负整数 $a_i, b_i, c_i$ ($0 \leq a_i, b_i \leq c_i \leq 10^9$)，表示第 $i$ 个站台的初始人数，每个单位时刻增加的人数以及人数上限。
输出一行一个整数，表示需要召唤的火车数量的最小值。
为了方便，我们在最后加一个站台，初始时有 $N$ 个人，每一时刻会增加 $N$ 个人，人数上限为 $+ \infty$ (其中 $N$ 是一个充分大的数，比如 $2^{32}$)，容易证明这个操作不影响答案。
这样就可以保证一辆火车每次恰好送走 $K$ 个人。
我们使用玄学 DP，用 $f_{i, j}$ 表示只考虑前 $i$ 个站台，你要撑 $j$ 个单位时间，并且保持不输所需要召唤的火车的最少数目；$g_{i, j}$ 表示只考虑前 $i$ 个站台，撑 $j$ 单位时间保持不输，且将除了第 $i$ 个站台外的所有站台的人都接走所需要叫的火车的最少总数目。此外，我们把 $g_{i, j}$ 撑 $j$ 单位时间保持不输后叫的火车称为 "额外火车" (因为它是起 "清空" 作用的)。
注意，这两种状态均要求每次恰好接走 $K$ 个人，如果做不到这一点，则状态为 $+ \infty$。
于是边界为 $f_{0, j} = 0$，答案为 $f_{n, t}$。
考虑 $\left( i, j \right)$ 的转移，有如下两种情况：
前 $j$ 轮中没有一辆火车接走站台 $i$ 的人，即站台 $i$ 的所有人都是靠 "额外火车" 接走的。
于是，这种状态存在的充要条件是 $a_i + j \cdot b_i \leq c_i \wedge f_{i-1, j} < + \infty$。
此时 $f_{i, j} = f_{i-1, j}$，考虑 $g_{i, j}$，由于前 $i - 1$ 个站台在前 $j$ 时刻一共产生了 $\displaystyle L = \sum_{v < i} \left( a_v + j \cdot b_v \right)$ 个人，于是至少需要派 $\left \lceil \dfrac LK \right \rceil$ 辆火车来接走。
当然，为了保证每次恰好接走 $K$ 个人，因此总接的人数 $\left \lceil \dfrac LK \right \rceil \cdot K$ 不应超过当前前 $i$ 个站台的总人数 $\displaystyle \sum_{v \leq i} \left( a_v + j \cdot b_v \right)$。
即当且仅当 $\displaystyle \left \lceil \dfrac LK \right \rceil \cdot K \leq \sum_{v \leq i} \left( a_v + j \cdot b_v \right)$ 时，更新 $g_{i, j} = \left \lceil \dfrac LK \right \rceil$。
前 $j$ 轮中有火车接走站台 $i$ 的人。设最后一次是在 $r$ 单位时间。
因此，在前 $r$ 轮中也一定清空了前 $i - 1$ 个站台，共花了 $g_{i, r}$ 辆火车。
此时，设第 $i$ 个站台还有 $rem = a_i + r \cdot b_i - K \cdot g_{i, r}$ 个人，则它在剩下 $j - r$ 轮中会 "涨" 到 $rem + \left( j - r \right) \cdot b_i$。
于是，在这个时候，我们需要派 $need = \left \lceil \dfrac {\max \left\{ rem + \left( j - r \right) \cdot b_i - c_i, 0 \right\}} K \right \rceil$ "额外火车" 排除第 $i$ 个站台的 "潜在危险"。
还是为了每次恰好接走 $K$ 个人，因此必须保证接走的总人数 $need \cdot K \leq rem$。
如果 $need \cdot K \leq rem$ 成立，在剩下的 $j - r$ 轮中，由于不再动第 $i$ 个站台，相当于对前 $i - 1$ 个站台重新开始游戏。
不过此时需要有 $a_i = 0$，但这里并不麻烦，只需要在 DP 外面加一维，表示这 $i$ 个站台初始时是有 $a_i$ 个人的，还是空的。
考虑 $f_{i, j}$，对于 $i - 1$ 个站台，可以动 $j - r$ 轮，这个 DP 值就是 $f_{i-1, j-r}$ (ps: 不论前面的 $f$ 是什么，这里的 $f$ 都是初始时为空的时的状态)。
对 $g_{i, j}$ 来说，由于总人数为 $\displaystyle L = \left( j - r \right) \cdot \sum_{v < i} b_v$，因此需要派 $\left \lceil \dfrac LK \right \rceil$ 辆火车，和上面类似地判断一下是否保证每次恰好接走 $K$ 个人即可。
(在可行的情况下) 转移方程即为 $f_{i, j} \downarrow g_{i, r} + need + f_{i-1, j-r}, \ g_{i, j} \downarrow g_{i, r} + need + \left \lceil \dfrac {\left( j - r \right) \cdot \sum_{v < i} b_v} K \right \rceil$。
总时间复杂度为 $O \left( n t^2 \right)$。
#include <bits/stdc++.h>
typedef long long ll;
const int N = 254;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
int n, t, K;
int a[N], d[N];
ll A[N], D[N], lim[N];
ll f[N][N][2], g[N][N][2];
// f : last people, g : last train to empty (and not exceed)
inline void down(ll &x, const ll y) {x > y ? x = y : 0;}
inline ll max(const ll x, const ll y) {return x < y ? y : x;}
int main() {
int i, j, k, r; ll times, time2, rem, need;
scanf("%d%d%d", &n, &t, &K);
for (i = 1; i <= n; ++i) scanf("%d%d%lld", a + i, d + i, lim + i);
++n, a[n] = d[n] = INT_MAX, lim[n] = INF;
for (i = 1; i <= n; ++i) A[i] = A[i - 1] + a[i], D[i] = D[i - 1] + d[i];
memset(f, 63, sizeof f), memset(g, 63, sizeof g);
memset(f, 0, sizeof*f), memset(g, 0, sizeof*g);
for (i = 1; i <= n; ++i)
for (j = 0; j <= t; ++j)
for (k = 0; k < 2; ++k) {
if ((ll)k * a[i] + (ll)j * d[i] <= lim[i] && f[i - 1][j][k] < INF) {
down(f[i][j][k], f[i - 1][j][k]), times = (k * A[i - 1] + j * D[i - 1] + K - 1) / K;
if (times * K <= k * A[i] + j * D[i]) down(g[i][j][k], times);
}
for (r = 0; r < j; ++r) if ((times = g[i][r][k]) < INF) {
rem = k * A[i] + r * D[i] - K * times, assert(rem >= 0);
need = (max(0, rem + (ll)(j - r) * d[i] - lim[i]) + K - 1) / K;
if (need * K <= rem && f[i - 1][j - r][0] < INF) {
down(f[i][j][k], times + need + f[i - 1][j - r][0]);
time2 = ((j - r) * D[i - 1] + K - 1) / K;
if (time2 * K <= (j - r) * D[i] + (rem - need * K)) down(g[i][j][k], times + need + time2);
}
}
}
printf("%lld\n", f[n][t][1]);
return 0;
}
坑1：尤其要注意 "保证恰好接走 $K$ 个人" 的性质，这是这道题的点睛之笔，如果不加上这个限制，则整个状态是无法转移的。
坑2：注意答案可能会超过 int，需要使用 long long。