自动搬运

查看原文

来自洛谷，原作者为

	Aaron_Romeo 鸟在笼中，恨关羽不能张飞；王生理塘，虽文丑奈何颜良。

搬运于2025-08-24 22:54:13，当前版本为作者最后更新于2024-05-29 22:12:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

小数肯定做不了，但是注意到将所有区间 $(l,r)$ 改成 $[l,r)$ 后就可以把值域变成整数了。

心路历程

想直接看正解就跳过。

贪心应该不好做，最长路还不如 dp。不如就考虑 dp。

比如说将所有点离散化一下，$dp_{i,j,b}$ 表示当前在(离散化后)第 $i$ 个点，位于教室 $j$，从 $i$ 花 $k$ 的代价走到另一个教室此时放的幻灯片有没有看过(没放片就当没看过)时最多看过多少片。虽然但是，我可能中间不能存档(如下图)，这样的话转移会非常麻烦，就很难过。

然后再考虑解决这个问题，比如说每两个点之间我只记录片看得最多的那个人，看得片一样多就取最快的。仔细想想发现可能不优(原因这里因为我懒所以不多赘述)。

接着就不会了。看了看题解，发现要将离散化连根刨掉。

状态还是 $dp_{i,j,b}$，只是 $i$ 变成了当前在 $i$ 这个位置，注意现在没有离散化。

转移很简单，时间复杂度可以做到 $O(k)$。

如何优化？

显然对于同一 $j,b$，$dp_{i,j,b}$ 随 $i$ 单调递增，且对于值相同的两个人，假如说是 $x$ 和 $y$，那么 $dp_{x,j,b}$ 仅通过原地挂机就能得到 $dp_{y,j,b}$（当然 $b$ 可能会从 $1$ 变为 $0$，但并不影响 $x$ 比 $y$ 更优）。

而 $dp_{i,j,b}$ 的值域是 $O(n)$ 的，此时套路告诉我们交换 $i$ 和 $dp_{i,j,b}$，即每种值只记录最快的那个人来代替其他人转移。

正解

重新定义一下状态，$dp_{i,j,b}$ 表示看过 $i$ 部片子，当前位于教室 $j$，花 $k$ 的代价走到另一个教室此时放的幻灯片有没有看过(没放片就当没看过)时最快在哪个位置。

转移的话考虑看的下一部片在哪个教室。如果在当前教室就直接跳，否则在另一个教室那么现在就出发肯定是最优的(注意可能在当前教室再向前走几步可以使得 $b$ 从 $1$ 变为 $0$，但是不转移他显然不影响答案)。

然后用二分维护一下转移就做完了，更多细节见代码。

Code

#include <iostream>
#include <algorithm>
#include <cstring>
typedef long long ll;
const int N = 3e5;
const int INF = 0x3f3f3f3f;
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1 ++ )
inline bool is_num(char ch) {return '0' <= ch && ch <= '9';}
inline bool is_char(char ch) {return 'a' <= ch && ch <= 'z' || 'A' <= ch && ch <= 'Z';}
char buf[1000005], *p1 = buf, *p2 = buf;
inline int read()
{
	char ch;
	int f = 1, x = 0;
	while (!is_num(ch = gc())) if (ch == '-') f = -1;
	do x = (x << 1) + (x << 3) + ch - '0'; while (is_num(ch = gc()));
	return f * x;
}
int n[2], m;
int dp[2][2][2];
struct node
{
	int l, r;
	bool operator < (const node &t) const {return l < t.l;}
	bool operator < (const int &t) const {return r < t;}
} block[2][N + 5];
inline int get(int type, int pos) {return std :: lower_bound(block[type] + 1, block[type] + n[type] + 1, pos) - block[type];}
inline int find(int type, int pos) {int t = get(type, pos); return block[type][t].l <= pos ? t : 0;} // 在 type 教室的 pos 位置放的是哪部片子，没放返回 0
inline int next(int type, int pos) {int t = get(type, pos); return t + (block[type][t].l <= pos);} // 在 type 教室的 pos 位置的下一部片是谁
inline void modify(int &x, int y) {x = std :: min(x, y);}
int main()
{
	n[0] = read() + 1, n[1] = read() + 1, m = read();
	for (int i = 1; i < n[0]; i ++ ) block[0][i] = /* */ {read(), read() - 1}; block[0][n[0]] = /* */ {INF, INF}; std :: sort(block[0] + 1, block[0] + n[0] + 1);
	for (int i = 1; i < n[1]; i ++ ) block[1][i] = /* */ {read(), read() - 1}; block[1][n[1]] = /* */ {INF, INF}; std :: sort(block[1] + 1, block[1] + n[1] + 1);
	std :: memset(dp, 0x3f, sizeof dp);
	dp[!block[0][1].l][0][0] = 0;
	int res = 0;
	for (int i = !block[0][1].l; i <= n[0] + n[1]; i ++ )
	{
		std :: memset(dp[i + 1 & 1], 0x3f, sizeof dp[i + 1 & 1]);
		for (int cas = 0; cas <= 1; cas ++ ) // 注意因为可能会出现 i 更新 i, 所以要么选择更新两遍，要么类似于 dijkstra 将值从小到大更新
			for (int j = 0; j <= 1; j ++ )
				for (int k = 0; k <= 1; k ++ )
				{
					if (dp[i & 1][j][k] >= INF) continue;
					int tim = dp[i & 1][j][k], pos = find(j, tim), across = find(j ^ 1, tim + m), after = next(j, tim);
					modify(dp[i + (across && !k) & 1][j ^ 1][pos && find(j, tim + 2 * m) == pos], tim + m); // 下一部片在另一个教室，立即出发
					modify(dp[i + 1 & 1][j][across && k && find(j ^ 1, block[j][after].l + m) == across], block[j][after].l); // 下一部片在当前教室
					res = std :: max(res, i);
				}
	}
	printf("%d", res);
	return 0;
}