题目描述

有 $n$ 个站台,从左往右编号为 $1, 2, \cdots, n$,每个站台初始时 ($0$ 时刻) 有 $a_i$ 个人。

每个时刻,会依次发生如下事件:

  1. 你可以选择召唤一辆向右行驶的火车 (最大载客量为 $K$),接走所有站台上从左往右数的前 $K$ 个人。

    如果所有站台上的总人数不足 $K$,则接走所有站台上的人。

    这个过程你可以执行任意多次 (即在同一时刻可以召唤任意辆火车)。

  2. 在该时刻末,第 $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)$ 的转移,有如下两种情况:

  1. 前 $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$。

  2. 前 $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