T1 街景整修（skyline）

简要题意

给定从左到右的 $N$ 座建筑高度，$2\le N\le10^5$、$1\le H_i\le10^9$。至多修改一座建筑的高度为任意正整数，不改变顺序，求相邻高度差绝对值之和的最小值。至多 $10$ 组，$\sum N\le3\times10^5$，逐组输出一个整数。

一句话题解

枚举修改位置，只重算受影响的邻边；内部位置修改后的最小贡献就是左右邻居的高度差。

完整题解

25 分：非降高度

非降时，原总落差为 $H_N-H_1$。对于任何内部位置，左右两项原来已经相加等于两侧的高度差，修改不能让它变小；修改首尾则可以把唯一相邻差消为 $0$。因此只需在两端选节省较多的一端。

时间 $O(N)$，空间 $O(N)$。在一般序列中只改端点是不完整做法。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, a[N], b[N];
LL total() {
	LL s = 0;
	for (int i = 2; i <= n; i ++) s += abs(a[i] - a[i - 1]);
	return s;
}
int gain(int i) {
	if (i == 1) return abs(a[1] - a[2]);
	if (i == n) return abs(a[n] - a[n - 1]);
	return abs(a[i] - a[i - 1]) + abs(a[i] - a[i + 1]) - abs(a[i - 1] - a[i + 1]);
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n;
		int high = 0;
		for (int i = 1; i <= n; i ++) cin >> a[i], high = max(high, a[i]);
		LL sum = total(), ans = sum;
		ans -= max(gain(1), gain(n));
		cout << ans << "\n";
	}
	return 0;
}

45 分：完整枚举加非降分支

在 $N,H_i\le100$ 时，枚举被修改的位置和修改后的高度，每次重新扫描全部相邻差求和，时间 $O(N^2H)$，其中 $H=\max H_i$。

为什么只枚举 $1\sim H$ 即可？将一个超出原高度范围的新高度向范围内部移动，不会增加它与任一邻居的距离，所以至少有一个最优方案的新高度在此范围内。

在程序中先判断非降序列并使用上一节做法，其他情况完整枚举，就能兼得前两档的 $45$ 分。不带非降分支的通用暴力只对应 $20$ 分，因为第一档的 $N$ 并不小。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, a[N], b[N];
LL total() {
	LL s = 0;
	for (int i = 2; i <= n; i ++) s += abs(a[i] - a[i - 1]);
	return s;
}
int gain(int i) {
	if (i == 1) return abs(a[1] - a[2]);
	if (i == n) return abs(a[n] - a[n - 1]);
	return abs(a[i] - a[i - 1]) + abs(a[i] - a[i + 1]) - abs(a[i - 1] - a[i + 1]);
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n;
		int high = 0;
		for (int i = 1; i <= n; i ++) cin >> a[i], high = max(high, a[i]);
		LL sum = total(), ans = sum;
		if (is_sorted(a + 1, a + n + 1)) {
			cout << sum - max(gain(1), gain(n)) << "\n";
			continue;
		}
		for (int i = 1; i <= n; i ++) {
			int old = a[i];
			for (int x = 1; x <= high; x ++) {
				a[i] = x;
				ans = min(ans, total());
			}
			a[i] = old;
		}
		cout << ans << "\n";
	}
	return 0;
}

65 分：只重算相邻贡献

修改位置 $i$ 时，只有 $(i-1,i)$ 和 $(i,i+1)$ 两条邻边可能改变。记它们原来的贡献为 $old$，试改为 $x$ 的新贡献为 $now$，则新总和为 $S-old+now$，不必重新扫描整条街。

枚举位置和新高度，时间降为 $O(NH)$，可解决 $N,H_i\le1000$ 的前两个规模档；再保留非降分支，累计 $65$ 分。若不处理非降大数据，这份慢解只对应 $40$ 分。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, a[N], b[N];
LL total() {
	LL s = 0;
	for (int i = 2; i <= n; i ++) s += abs(a[i] - a[i - 1]);
	return s;
}
int gain(int i) {
	if (i == 1) return abs(a[1] - a[2]);
	if (i == n) return abs(a[n] - a[n - 1]);
	return abs(a[i] - a[i - 1]) + abs(a[i] - a[i + 1]) - abs(a[i - 1] - a[i + 1]);
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n;
		int high = 0;
		for (int i = 1; i <= n; i ++) cin >> a[i], high = max(high, a[i]);
		LL sum = total(), ans = sum;
		if (is_sorted(a + 1, a + n + 1)) {
			cout << sum - max(gain(1), gain(n)) << "\n";
			continue;
		}
		for (int i = 1; i <= n; i ++) {
			int old = (i > 1 ? abs(a[i] - a[i - 1]) : 0) + (i < n ? abs(a[i] - a[i + 1]) : 0);
			for (int x = 1; x <= high; x ++) {
				int now = (i > 1 ? abs(x - a[i - 1]) : 0) + (i < n ? abs(x - a[i + 1]) : 0);
				ans = min(ans, sum - old + now);
			}
		}
		cout << ans << "\n";
	}
	return 0;
}

另一条 $65$ 分路线：已发现最优高度可取某个邻居，但每次试改后仍扫描全数组求和，总时间 $O(N^2)$；同样要结合非降分支。两种慢解体现的是不同优化层次，不能混为同一份代码。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, a[N], b[N];
LL total() {
	LL s = 0;
	for (int i = 2; i <= n; i ++) s += abs(a[i] - a[i - 1]);
	return s;
}
int gain(int i) {
	if (i == 1) return abs(a[1] - a[2]);
	if (i == n) return abs(a[n] - a[n - 1]);
	return abs(a[i] - a[i - 1]) + abs(a[i] - a[i + 1]) - abs(a[i - 1] - a[i + 1]);
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n;
		int high = 0;
		for (int i = 1; i <= n; i ++) cin >> a[i], high = max(high, a[i]);
		LL sum = total(), ans = sum;
		if (is_sorted(a + 1, a + n + 1)) {
			cout << sum - max(gain(1), gain(n)) << "\n";
			continue;
		}
		for (int i = 1; i <= n; i ++) {
			int old = a[i];
			if (i > 1) a[i] = a[i - 1], ans = min(ans, total());
			if (i < n) a[i] = a[i + 1], ans = min(ans, total());
			a[i] = old;
		}
		cout << ans << "\n";
	}
	return 0;
}

满分：直接计算局部最优

设原总落差为 $S$。

• 若改第一座或最后一座，将其高度改成唯一邻居的高度即可，把这条邻边贡献消为 $0$。
• 若改内部位置 $i$，需要最小化 $|H_{i-1}-x|+|x-H_{i+1}|$。

由绝对值的三角不等式，后者不小于 $|H_{i-1}-H_{i+1}|$。当 $x$ 取两侧高度之间的任意整数时均能取等，尤其直接取任一个邻居高度就可以。因此内部位置能够减少的总落差为

$$|H_{i-1}-H_i|+|H_i-H_{i+1}|-|H_{i-1}-H_{i+1}|.$$

枚举所有位置，取最大减少量 $best$，答案为 $S-best$。这既不漏方案，也不虚构不可达的更小值：每个局部下界都有合法高度达到，且修改不影响其他相邻差。

时间 $O(N)$，空间 $O(N)$。使用全局数组；$N=2$ 时循环内部为空，两端直接给出答案 $0$。总和可达到 $99999\times(10^9-1)$，必须用 long long 保存；单条差及两条差之和小于 $2\times10^9$，标程的局部减少量可以用 int。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, a[N];
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n;
		for (int i = 1; i <= n; i ++) cin >> a[i];
		LL sum = 0;
		for (int i = 2; i <= n; i ++) sum += abs(a[i] - a[i - 1]);
		int best = max(abs(a[1] - a[2]), abs(a[n] - a[n - 1]));
		for (int i = 2; i < n; i ++) {
			int t = abs(a[i] - a[i - 1]) + abs(a[i] - a[i + 1]);
			best = max(best, t - abs(a[i - 1] - a[i + 1]));
		}
		cout << sum - best << "\n";
	}
	return 0;
}

常见误区与赛时识别

• 只减去最大一条邻边：$[1,2,1]$ 的答案是 $0$，因为修改中间位置同时影响两条邻边。
• 只考虑内部位置：$[1,2,3]$ 的答案是 $1$，最优修改在端点。
• 只改全局最高或最低的建筑，即使把所有并列极值与两个端点都试过，也可能漏掉中间高度的局部峰谷。极端高低值位于平台时，改它们未必有收益。
• 选若干最大邻边，再只检查其端点：最大邻边可能位于长平台之间，另一处较小的两条邻边却能同时缩短。多试几条最大边并不能构成证明。
• 只比较修改前的两条邻边之和：必须减掉修改后仍无法消除的两侧高度差。
• 多组数据只清总和、不清最优减少量：前组的较大值可能使下一组答案错误甚至为负数。

赛时先问“改一个位置会影响哪几项”，再问“这几项能降到多少”。无需模拟施工过程，也不需要动态规划。

T2 研习计划（study）

简要题意

每组给定 $N$ 门课程、$M$ 周，以及听课增量 $A_i$ 和自习增量 $B_i$。每周按编号各安排一节课，所有课程的初始熟练度为 $0$；在某科的课时可以听本课，也可以自习任意一科，包括当前课程。求 $NM$ 节课结束后，所有课程最低熟练度的最大值。$1\le N\le3\times10^5$，$1\le M,A_i,B_i\le10^9$；至多 $10$ 组，同一文件 $\sum N\le6\times10^5$，每组输出一个整数。

一句话题解

将固定课表转成每科至多 $M$ 次的高收益机会和可以调配的公共课时，二分目标熟练度，检查所需课时总和是否超出 $NM$。

完整题解

先分清课程与课时

课表规定的是当前可以听哪门课，不是这节课必须学习哪门课。只要选择自习，就能学习任意课程。另一方面，听课机会不能凭空转移：课程 $i$ 总共只有 $M$ 节本课。

还要注意 $A_i$ 不一定大于 $B_i$。在课程 $i$ 的课时里，可以自习课程 $i$，因此这类专属课时的最好收益为

$$C_i=\max(A_i,B_i).$$

对同一门课程，先使用收益为 $C_i$ 的专属机会不会比先自习更差。最多使用 $M$ 次以后，再增加熟练度只能依靠收益为 $B_i$ 的自习。

二分最低熟练度

假设要求所有课程的熟练度至少达到 $X$。第 $i$ 门课程至少需要的课时数为

$$d_i=\begin{cases} \left\lceil X/C_i\right\rceil,&X\le MC_i,\\ M+\left\lceil (X-MC_i)/B_i\right\rceil,&X>MC_i. \end{cases}$$

只要判断 $\sum d_i\le NM$，便可以决定目标 $X$ 是否可行。

必要性。 每科至多有 $M$ 次高收益机会，其余学习每次只增加 $B_i$。优先使用高收益机会时，仍至少需要 $d_i$ 次；全部课程的学习次数不能超过总课时。

充分性。 对每科，先把 $\min(d_i,M)$ 次学习放入它自己的课时。需要超过 $M$ 次的课程，将额外需求放入其他课程释放的课时。若 $\sum d_i\le NM$，总空位一定足够。这些收益没有先后依赖、遗忘或中途检查，因此分配好课时后，按原课表的顺序执行即可。未使用的课时任意安排，也不会降低熟练度。

因此，固定课表确实可以抽象成课时总量，而不是忽略了时间顺序。可行性关于 $X$ 单调，进行整数二分即可。所有课时的单次收益不超过 $\max C_i$，故最低值不超过平均值 $M\max C_i\le10^{18}$。

时间复杂度为 $O(N\log 10^{18})$，空间复杂度为 $O(N)$。

部分分与赛时路线

路线	可解决的公开范围	做法	得分
单周	$M=1$	每科只学一次，取 $\min\max(A_i,B_i)$	10
逐次分配	$NM\le3\times10^5$	最小堆维护当前最低熟练度，每次提升它	60
全自习	所有 $A_i=B_i$	二分并检查 $\sum\lceil X/B_i\rceil\le NM$	55
特殊性质组合	全自习，加上单周公式	分情况处理	65
小总课时与相等收益组合	小乘积用堆，其余用全自习判定	合并两个自然子问题	90
完整模型	全部范围	分段计算每科需求	100

单周时，每科要有正的熟练度，至少需要一次学习，而总共恰有 $N$ 次；所以不能把某科安排两次而让另一科一次也没有。每科在自己的课时取收益 $C_i$ 最优。

最小堆路线不是按真实课表逐节贪心。它先在抽象模型里分配每门课程的学习次数：第 $i$ 科前 $M$ 次增加 $C_i$，以后增加 $B_i$。对任意目标 $X$，当堆顶尚小于 $X$ 时，这门课程仍必须继续提升；该过程达到全部不小于 $X$ 恰需 $\sum d_i$ 步。因此做满 $NM$ 步得到最优最低值，再由充分性证明还原出合法课表安排。复杂度为 $O(NM\log N)$。

55 分与 60 分覆盖的是不同测试点，不能直接相加。组合以后共有 90 分；最后 10 分要求一般情况的完整判定。这保留了原题自然子问题占主要分数的特点。

部分分参考实现

单周公式。下面的程序让每科独立学习 $M$ 次；当 $M=1$ 时这是最优方案，一般情况下可能不如跨科调配。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3e5 + 10;
int n;
LL m, a[N], b[N];
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> m;
		for (int i = 1; i <= n; i ++) cin >> a[i];
		for (int i = 1; i <= n; i ++) cin >> b[i];
		LL ans = 1e9;
		for (int i = 1; i <= n; i ++) ans = min(ans, max(a[i], b[i]));
		cout << m * ans << "\n";
	}
	return 0;
}

逐次分配的 60 分做法：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3e5 + 10;
struct Node {
	LL val, cnt;
	int id;
	bool operator < (const Node &t) const {
		if (val != t.val) return val > t.val;
		return id > t.id;
	}
};
int n;
LL m, a[N], b[N];
priority_queue<Node> q;
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> m;
		for (int i = 1; i <= n; i ++) cin >> a[i];
		for (int i = 1; i <= n; i ++) cin >> b[i];
		while (!q.empty()) q.pop();
		for (int i = 1; i <= n; i ++) q.push({0, 0, i});
		for (LL i = 1; i <= n * m; i ++) {
			Node t = q.top();
			q.pop();
			t.val += t.cnt < m ? max(a[t.id], b[t.id]) : b[t.id];
			t.cnt ++;
			q.push(t);
		}
		cout << q.top().val << "\n";
	}
	return 0;
}

全自习的 55 分做法：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3e5 + 10;
int n;
LL m, a[N], b[N];
bool check(LL x) {
	LL cnt = 0;
	for (int i = 1; i <= n; i ++) {
		LL c = b[i];
		cnt += (x + c - 1) / c;
		if (cnt > n * m) return false;
	}
	return true;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> m;
		for (int i = 1; i <= n; i ++) cin >> a[i];
		for (int i = 1; i <= n; i ++) cin >> b[i];
		LL l = 0, r = 1e18;
		while (l < r) {
			LL mid = l + (r - l + 1) / 2;
			if (check(mid)) l = mid;
			else r = mid - 1;
		}
		cout << l << "\n";
	}
	return 0;
}

单周加全自习的 65 分组合：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3e5 + 10;
int n;
LL m, a[N], b[N];
bool check(LL x) {
	LL cnt = 0;
	for (int i = 1; i <= n; i ++) {
		LL c = b[i];
		cnt += (x + c - 1) / c;
		if (cnt > n * m) return false;
	}
	return true;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> m;
		for (int i = 1; i <= n; i ++) cin >> a[i];
		for (int i = 1; i <= n; i ++) cin >> b[i];
		if (m == 1) {
			LL ans = 1e9;
			for (int i = 1; i <= n; i ++) ans = min(ans, max(a[i], b[i]));
			cout << ans << "\n";
			continue;
		}
		LL l = 0, r = 1e18;
		while (l < r) {
			LL mid = l + (r - l + 1) / 2;
			if (check(mid)) l = mid;
			else r = mid - 1;
		}
		cout << l << "\n";
	}
	return 0;
}

小总课时加全自习的 90 分组合：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3e5 + 10;
struct Node {
	LL val, cnt;
	int id;
	bool operator < (const Node &t) const {
		if (val != t.val) return val > t.val;
		return id > t.id;
	}
};
int n;
LL m, a[N], b[N];
priority_queue<Node> q;
bool check(LL x) {
	LL cnt = 0;
	for (int i = 1; i <= n; i ++) {
		LL c = b[i];
		cnt += (x + c - 1) / c;
		if (cnt > n * m) return false;
	}
	return true;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> m;
		for (int i = 1; i <= n; i ++) cin >> a[i];
		for (int i = 1; i <= n; i ++) cin >> b[i];
		if (n * m <= 300000) {
			while (!q.empty()) q.pop();
			for (int i = 1; i <= n; i ++) q.push({0, 0, i});
			for (LL i = 1; i <= n * m; i ++) {
				Node t = q.top();
				q.pop();
				t.val += t.cnt < m ? max(a[t.id], b[t.id]) : b[t.id];
				t.cnt ++;
				q.push(t);
			}
			cout << q.top().val << "\n";
		} else {
			LL l = 0, r = 1e18;
			while (l < r) {
				LL mid = l + (r - l + 1) / 2;
				if (check(mid)) l = mid;
				else r = mid - 1;
			}
			cout << l << "\n";
		}
	}
	return 0;
}

容易走错的方向

1. 把 $C_i$ 当成无限次收益。 $N=2,M=2,A=(2,6),B=(1,1)$ 时，答案为 $5$；若无限使用 $C_i$，会错误得到 $6$。不过该做法在单周与 $A=B$ 时都正确，本来就应有 65 分，不能把这些分数当成数据漏洞。
2. 每科固定学习 $M$ 次。 $N=2,M=3,A=B=(1,2)$ 时，给两科分别分配四次、两次学习可使最低熟练度为 $4$；固定各学三次只能得到 $3$。
3. 按真实课表，每节课都选择当前最低的课程。 这可能错过高收益的专属听课机会。即使并列时优先当前课程，也没有解决这种时间安排上的短视。例如 $N=2,M=2,A=(6,18),B=(20,2)$，正确方案是两个课程 1 的课时都自习课程 1，两个课程 2 的课时都听课，得到 $(40,36)$；这种贪心却得到 $(20,38)$，最低值只有 $20$。堆解需要先抽象分配次数，不能和这一策略混为一谈。
4. 把课时切碎。 学习次数必须为整数，每科都要向上取整，不能先求出连续资源的解再简单取整。
5. 没有归一化 $A_i$ 与 $B_i$。 自习本课也是合法选择，不能强迫先使用效率更低的听课机会。

实现边界与满分代码

答案可达 $10^{18}$，$NM$ 可达 $3\times10^{14}$，都要使用 long long。单科需求能安全放入 64 位，但全部需求不加限制地求和可能溢出：每次累加后，一旦已经超过 $NM$，立即返回不可行即可。这样累加前的值不超过 $NM$，再加一项也不会超出 64 位。

向上取整使用 $(x+y-1)/y$；二分中点使用 $l+(r-l+1)/2$。每组重新读入数组并初始化二分边界。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3e5 + 10;
int n;
LL m, a[N], b[N];
bool check(LL x) {
	LL cnt = 0;
	for (int i = 1; i <= n; i ++) {
		if (x <= m * a[i]) cnt += (x + a[i] - 1) / a[i];
		else cnt += m + (x - m * a[i] + b[i] - 1) / b[i];
		if (cnt > n * m) return false;
	}
	return true;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> m;
		for (int i = 1; i <= n; i ++) cin >> a[i];
		LL mx = 0;
		for (int i = 1; i <= n; i ++) {
			cin >> b[i];
			a[i] = max(a[i], b[i]);
			mx = max(mx, a[i]);
		}
		LL l = 0, r = m * mx;
		while (l < r) {
			LL mid = l + (r - l + 1) / 2;
			if (check(mid)) l = mid;
			else r = mid - 1;
		}
		cout << l << "\n";
	}
	return 0;
}

T3 寻食路线（forage）

简要题意

给定平面上 $N$ 个互异且不在原点的整数坐标投喂点（$1\le N\le2000$，坐标绝对值不超过 $10000$），小狐狸从原点出发，每次前往另一个投喂点并得到一份食物，后一次移动距离必须严格小于前一次。投喂点可以重复到达并重复领取食物，但原点不能作为后续目的地。求一条路线最多能取得的食物份数。输入至多 $10$ 组，同一文件的 $\sum N^2\le8\times10^6$，每组输出一个最大值。

一句话题解

将所有点对按距离平方递增排序，维护从各点出发的最优后续路线，同距离的转移统一读取旧值并在整批结束后更新。

完整题解

一、先保留上一步的距离

不能因为站在同一个点，就把两种路线的状态合并：上一步走了多远，会限制下一步能去哪里。也不能给每个投喂点打一个永久的访问标记，因为题目允许重访。

把原点编号记为 $0$，投喂点编号为 $1\sim N$。用距离平方 $d(u,v)$ 比较远近即可，不必开平方。坐标范围保证距离平方不超过 $8\times10^8$，使用 int 足够。

设 $F(p,u)$ 表示刚从 $p$ 来到 $u$ 后，从本次到达开始最多能得到多少份食物。本次到达贡献一份，故

$$F(p,u)=1+\max_{1\le v\le N,\ v\ne u,\ d(u,v)<d(p,u)}F(u,v),$$

没有合法下一站时，最大值按 $0$ 处理。最终答案是 $\max_{1\le u\le N}F(0,u)$。

虽然点可以反复出现，但状态的边长严格变短，不会出现状态依赖环。

二、20 分：显式枚举边状态之间的转移

把每个合法的有向点对 $(p,u)$ 看成一个状态，且 $u\ne0$。将这些状态按距离平方从小到大排序，每处理一个状态，就枚举所有已经处理过的状态，检查它是否形如 $(u,v)$ 且距离严格更短。符合时转移。

共有 $O(N^2)$ 个状态，每个状态枚举 $O(N^2)$ 个前驱状态，时间 $O(N^4)$，空间 $O(N^2)$，对应 $N\le50$ 的 20 分范围。这是直观的显式状态图写法，不是纯路线 DFS；没有记忆化的纯 DFS 在 $N=50$ 下没有运行时间保证。

#include<bits/stdc++.h>
using namespace std;
const int N = 2010, M = 4010000;
struct Edge {
	int a, b, d;
	bool operator< (const Edge &t) const {
		return d < t.d;
	}
} e[M];
int n, cnt, x[N], y[N], f[M];
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n;
		for (int i = 1; i <= n; i ++) cin >> x[i] >> y[i];
		cnt = 0;
		for (int i = 0; i <= n; i ++)
			for (int j = 1; j <= n; j ++) {
				if (i == j) continue;
				int dx = x[i] - x[j], dy = y[i] - y[j];
				e[++ cnt] = {i, j, dx * dx + dy * dy};
			}
		sort(e + 1, e + cnt + 1);
		int ans = 0;
		for (int i = 1; i <= cnt; i ++) {
			f[i] = 1;
			for (int j = 1; j < i; j ++)
				if (e[j].a == e[i].b && e[j].d < e[i].d) f[i] = max(f[i], f[j] + 1);
			if (!e[i].a) ans = max(ans, f[i]);
		}
		cout << ans << "\n";
	}
	return 0;
}

三、60 分：直接枚举下一站

状态 $(p,u)$ 的下一条边必须从 $u$ 出发，因此不需要扫描所有边状态，直接枚举下一站 $v$ 即可。对上述递推式记忆化，或按状态边长递增顺序迭代，时间都是 $O(N^3)$，空间 $O(N^2)$，覆盖前 12 个测试点，累计 60 分。

下面采用迭代版本，不依赖递归栈。记忆化是同样正确的 60 分路线；严格下降保证递归会终止，但这不等于可以忽略具体环境中的栈容量。

#include<bits/stdc++.h>
using namespace std;
const int N = 2010, M = 4010000;
struct Edge {
	int a, b, d;
	bool operator< (const Edge &t) const {
		return d < t.d;
	}
} e[M];
int n, cnt, x[N], y[N], d[N][N], f[N][N];
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n;
		for (int i = 1; i <= n; i ++) cin >> x[i] >> y[i];
		cnt = 0;
		for (int i = 0; i <= n; i ++)
			for (int j = 0; j <= n; j ++) {
				int dx = x[i] - x[j], dy = y[i] - y[j];
				d[i][j] = dx * dx + dy * dy;
				f[i][j] = 0;
				if (j && i != j) e[++ cnt] = {i, j, d[i][j]};
			}
		sort(e + 1, e + cnt + 1);
		int ans = 0;
		for (int i = 1; i <= cnt; i ++) {
			int a = e[i].a, b = e[i].b, res = 1;
			for (int v = 1; v <= n; v ++)
				if (v != b && d[b][v] < e[i].d) res = max(res, f[b][v] + 1);
			f[a][b] = res;
			if (!a) ans = max(ans, res);
		}
		cout << ans << "\n";
	}
	return 0;
}

四、满分：让距离顺序替我们维护限制

观察转移只关心“下一条边比当前边短”，而不关心上一条边的具体编号。可以按边长统一推进，使每个点只保留一个当前最优值。

列出含原点在内的所有无序点对，并按距离平方递增排序。处理距离平方为 $D$ 的一批边之前，令 $f[u]$ 表示：从 $u$ 出发，第一步的距离平方严格小于 $D$ 时，最多还能得到多少份食物。这里不计算站在 $u$ 本身的食物，初值均为 $0$。

对于这一批中的边 $(u,v)$，可以先去 $v$，得到一份食物，再接上从 $v$ 出发、首步更短的路线。因此用旧的 $f[v]+1$ 尝试更新 $u$。若 $u\ne0$，还可以反向走这条边，用旧的 $f[u]+1$ 尝试更新 $v$。当 $u=0$ 时不能更新反方向，因为原点不是合法的后续目的地。

同一距离的边必须整批处理：候选答案放在临时数组 $g$，所有转移都读取更新前的 $f$，整批结束后才将 $g$ 写回。否则后处理的边可能使用了同距离边刚产生的状态，错误地允许连续走等长的两段。

为了避免每批都清空长度为 $N$ 的数组，标程使用时间戳和一个记录本批涉及点的数组，只初始化、写回真正被更新的点。

五、正确性证明

按距离批次归纳。尚未处理任何边时，没有允许的移动，所有 $f[u]=0$，正确。

设处理本批前状态均正确。一条新增允许的非空路线，第一步要么是更短的边，此时已经包含在旧值中；要么恰好使用本批边 $(u,v)$。后一种情况下，剩余路线的第一步必须更短，根据归纳假设，最优后续恰由旧的 $f[v]$ 表示，所以候选值为 $1+f[v]$。程序枚举了所有合法的第一步，不允许走向原点，同批之间也不会串用更新。因此本批结束后，每个点的状态都恰为允许本批及更短边时的最优值。

处理全部边后，从原点出发的全部合法第一步都已考虑，故 $f[0]$ 就是答案。

六、复杂度与实现要点

无序边数为 $N(N+1)/2$。排序时间 $O(N^2\log N)$，转移时间 $O(N^2)$，空间 $O(N^2)$。$N=2000$ 时有 $2001000$ 条边，标程的边数组约占 24 MiB。

每一步使用的距离都严格变短，答案不会超过全部不同点对的数量，int 足够。每组必须重置点状态和时间戳；坐标和边数组仅访问当前有效前缀。原点的坐标固定为 $(0,0)$，不从输入读取。

#include<bits/stdc++.h>
using namespace std;
const int N = 2010, M = 2010000;
struct Edge {
	int a, b, d;
	bool operator< (const Edge &t) const {
		return d < t.d;
	}
} e[M];
int n, cnt, x[N], y[N], f[N], g[N], tag[N], q[N], tot;
int dist(int a, int b) {
	int dx = x[a] - x[b], dy = y[a] - y[b];
	return dx * dx + dy * dy;
}
void update(int u, int value, int id) {
	if (tag[u] != id) {
		tag[u] = id;
		g[u] = f[u];
		q[++ tot] = u;
	}
	g[u] = max(g[u], value);
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n;
		for (int i = 1; i <= n; i ++) cin >> x[i] >> y[i];
		fill(f, f + n + 1, 0);
		fill(tag, tag + n + 1, 0);
		cnt = 0;
		for (int i = 0; i <= n; i ++)
			for (int j = i + 1; j <= n; j ++)
				e[++ cnt] = {i, j, dist(i, j)};
		sort(e + 1, e + cnt + 1);
		for (int l = 1, r; l <= cnt; l = r) {
			r = l;
			while (r <= cnt && e[r].d == e[l].d) r ++;
			tot = 0;
			for (int i = l; i < r; i ++) {
				int a = e[i].a, b = e[i].b;
				update(a, f[b] + 1, l);
				if (a) update(b, f[a] + 1, l);
			}
			for (int i = 1; i <= tot; i ++) f[q[i]] = g[q[i]];
		}
		cout << f[0] << "\n";
	}
	return 0;
}

七、容易走偏的方向

• 最近点优先很快消耗可用的距离；最远可行点优先也不保证留下最佳后续。即使枚举第一站，再对两种贪心取最大值，仍不是完整算法。
• 把答案限制为 $N$，或禁止重访，都会被官方样例中的六次到达反驳。
• 只给边排序而逐条立即更新，不能保证严格递减；反转相同长度边的编号顺序，也不能修复依赖同批新值的问题。
• 原点不是普通投喂点，反向更新含原点的边会允许非法中转。
• 将直线距离取整会把本来不同的长度误判为相等，直接比较精确的距离平方即可。

赛时建议先写出 $(p,u)$ 状态拿到 60 分，再观察它只需要查询“比当前距离短的后续”，自然引出距离排序和批处理，不必强行从一维状态猜起。

T4 增设停站（express）

简要题意

每组给出 $N$ 座等距车站、快车的 $M$ 个停站和中速车的总停站数 $K$。慢车每站停，快车和中速车只在各自选定车站停；经过一段相邻站间路程的时间分别为 $A,B,C$，满足 $B<C<A$。中速车必须包含所有快车站，允许换乘，但只能向编号增大的方向乘车。选择其余停站，使分别从 $1$ 号站出发、在 $T$ 分钟内可达的其他车站数最多，输出最大数量。$2\le N\le10^9$，$2\le M\le K\le3000$，$K\le N$，$A\le10^9$，$T\le10^{18}$；至多 $10$ 组，同文件 $\sum M,\sum K\le6000$。

一句话题解

用快车站把铁路分段，每段总在首个不可达站新增停站；各段的边际收益递减，反复把名额分配给当前收益最大的段。

完整题解

1. 20 分：直接枚举新增的两个停站

测试点 $1\sim4$ 保证 $N\le300$，且只需新增两个停站。枚举两个不是快车站的不同位置。对于一种方案，从左到右扫描所有站，维护最近的快车站 $s$ 和最近的中速车站 $p$。到当前站 $x$ 的最短时间为

$$B(s-1)+C(p-s)+A(x-p).$$

这条路线依次乘快车、中速车、慢车。最后一个不慢于中速车的乘车机会应尽量靠右：跳过更靠右的快车站或中速车站，都不会使到达更快。因而该扫描能正确统计可达站数。

枚举 $O(N^2)$ 个方案，每个方案扫描 $O(N)$ 个站，总时间 $O(N^3)$，空间 $O(N)$。下面的程序把枚举推广为选择全部 $K-M$ 个新增站，首档就是枚举两站；新增站较多时，方案数过大，枚举不再可行。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3010;
int n, m, k, s[N], chosen[N], ans;
LL a, b, c, t;
void evaluate() {
	int fast = 1, semi = 1, p = 2, q = 1, cnt = 0;
	for (int i = 2; i <= n; i ++) {
		if (p <= m && s[p] == i) fast = semi = i, p ++;
		if (q <= k - m && chosen[q] == i) semi = i, q ++;
		cnt += b * (fast - 1) + c * (semi - fast) + a * (i - semi) <= t;
	}
	ans = max(ans, cnt);
}
void dfs(int start, int cnt) {
	if (cnt == k - m) {
		evaluate();
		return;
	}
	for (int i = start; i <= n - (k - m - cnt) + 1; i ++) {
		if (binary_search(s + 1, s + m + 1, i)) continue;
		chosen[cnt + 1] = i;
		dfs(i + 1, cnt + 1);
	}
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int tests;
	cin >> tests;
	while (tests --) {
		cin >> n >> m >> k >> a >> b >> c >> t;
		for (int i = 1; i <= m; i ++) cin >> s[i];
		ans = 0;
		dfs(1, 0);
		cout << ans << "\n";
	}
	return 0;
}

2. 50 分：直接按停站位置做 DP

测试点 $1\sim10$ 都有 $N\le300$。令 $f[i][j]$ 表示：已经确定到 $i$ 为止的中速车停站，$i$ 本身是第 $j$ 个停站时，$1$ 号站以外已经能到达的站数最大值。初始 $f[1][1]=0$。

设 $s$ 是严格位于 $i$ 左侧的最后一个快车站。枚举上一个中速停站 $p$，必须满足 $s\le p<i$；否则会漏掉一个必停的快车站。

到达 $p$ 的最短时间为 $B(s-1)+C(p-s)$。在 $p$ 换乘慢车，可以计算出区间 $[p+1,i-1]$ 内有多少站可达。如果 $i$ 是快车站，到它只需 $B(i-1)$；否则需要 $B(s-1)+C(i-s)$。把这些新增可达站数加到 $f[p][j-1]$ 上即可转移。答案是 $f[N][K]$。

共有 $O(NK)$ 个状态，每次枚举 $O(N)$ 个前驱，小范围时间 $O(N^2K)$，空间 $O(NK)$。程序用全局二维数组保存小范围状态，超出数组范围的状态用稀疏表保存，转移方式不变，但仍无法处理完整范围；理解 $N\le300$ 的二维数组转移即可掌握这档做法。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 310;
int n, m, k, s[3010], f[N][N];
map<pair<int, int>, int> large;
LL a, b, c, t;
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int tests;
	cin >> tests;
	while (tests --) {
		cin >> n >> m >> k >> a >> b >> c >> t;
		for (int i = 1; i <= m; i ++) cin >> s[i];
		// 为了容纳较大输入，下面使用稀疏的状态表，转移仍逐个枚举站点。
		large.clear();
		memset(f, -0x3f, sizeof f);
		f[1][1] = 0;
		int last = 1, q = 2;
		for (int i = 2; i <= n; i ++) {
			bool is_fast = q <= m && s[q] == i;
			LL arrive = is_fast ? b * (i - 1) : b * (last - 1) + c * (i - last);
			for (int p = last; p < i; p ++) {
				LL left = t - b * (last - 1) - c * (p - last);
				int cnt = (left < 0 ? 0 : min((LL)i - p - 1, left / a)) + (arrive <= t);
				for (int j = 2; j <= k; j ++) {
					int old;
					if (p < N && j - 1 < N) old = f[p][j - 1];
					else {
						auto it = large.find({p, j - 1});
						old = it == large.end() ? -1e9 : it->second;
					}
					if (i < N && j < N) f[i][j] = max(f[i][j], old + cnt);
					else {
						auto key = make_pair(i, j);
						auto it = large.find(key);
						if (it == large.end()) large[key] = old + cnt;
						else it->second = max(it->second, old + cnt);
					}
				}
			}
			if (is_fast) last = i, q ++;
		}
		cout << (n < N && k < N ? f[n][k] : large[{n, k}]) << "\n";
	}
	return 0;
}

3. 满分模型：快车站之间相互独立

快车最快，因此到快车站 $S_i$ 的最短时间固定为 $B(S_i-1)$，与其他区间新增哪些停站无关。

把铁路划分为 $[S_i,S_{i+1}-1]$，其中 $1\le i<M$。末站 $N$ 单独判断。每段左端是快车站；只需决定在该段内部增加几个停站，各段不会互相改变到达时间。

考虑其中一段 $[s,r]$。在位置 $p$ 停中速车后，先乘快车到 $s$，再乘中速车到 $p$，剩余时间为

$$L(p)=T-B(s-1)-C(p-s).$$

若 $L(p)<0$，这个停站没有收益；否则，从 $p$ 转慢车可以覆盖到

$$R(p)=\min\left(r,\ p+\left\lfloor\frac{L(p)}A\right\rfloor\right).$$

4. 一个区间内，把停站放在哪里

不新增停站时，从快车站 $s$ 换乘慢车已经能到达一个前缀。设当前首个尚不可达的位置为 $x$。

可以证明，存在一个最优方案把下一个有贡献的停站放在 $x$：

• 如果该停站在 $x$ 左侧，它覆盖到 $x$ 以后才有新增贡献。把它右移到 $x$，由于 $C<A$，最右覆盖位置不减，不会损失新增贡献。
• 如果下一个停站在 $x$ 右侧，设它为 $p$。把它及本段后续新增站整体左移 $p-x$ 格。每站的中速行程更短，因此它之后可乘慢车的距离不减；原有区间的间距没有增大，左侧空缺被补上，总可达数量不会减少。

重复该调整，可让每次新增停站都位于当前首个不可达位置。因此，知道该段目前可达前缀的右端，就能直接算出再增加一站的收益。

其收益为

$$g(x)=\min\left(r-x+1,\ \left\lfloor\frac{T-B(s-1)-C(x-s)}A\right\rfloor+1\right),$$

负剩余时间或 $x>r$ 时令收益为 $0$。随着 $x$ 右移，式中两项都不增，所以一段的连续新增收益构成非增序列。

5. 在各段之间分配名额

还需分配 $K-M$ 个停站名额。各段收益序列非增，而每段只能取一个前缀。

反复选择当前下一项收益最大的段即可。如果某个最优分配没有取当前最大项，却取了另一段不大于它的一项，可以用当前最大项替换对方已取前缀的最后一项，不破坏前缀条件，答案也不会减小。逐次交换可得到贪心分配，因而贪心最优。

每次直接扫描所有区段找最大值即可，无需使用堆。若全部收益都是 $0$，其余名额任意补到尚未停靠的站上，不改变答案；由于 $K\le N$，总能补足。不要把每个无收益的新停站硬算成一个可达站。

各段初始计数包含自己的左端快车站，不包含下一个快车站。最后单独计入可达的 $N$ 号站，并扣除起点 $1$，这样不重不漏。

6. 复杂度与实现边界

单组时间为 $O(M(K-M)+M)$，空间为 $O(M)$。因为 $M\le K\le3000$，$M(K-M)\le2250000$。同文件 $\sum K\le6000$，整体规模也足够小。

所有时间乘法使用 long long。先判断剩余时间是否为负，再作除法；C++ 的负整数除法向零截断，会把一些不可达站误算成可达。到达时间等于 $T$ 时仍应计数。每组都重新初始化当前区段位置和收益。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3010;
int n, m, k, s[N], pos[N], gain[N];
LL a, b, c, t;
int get_gain(int i) {
	if (pos[i] >= s[i + 1]) return 0;
	LL left = t - b * (s[i] - 1) - c * (pos[i] - s[i]);
	if (left < 0) return 0;
	return min((LL)s[i + 1] - pos[i], left / a + 1);
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int tests;
	cin >> tests;
	while (tests --) {
		cin >> n >> m >> k >> a >> b >> c >> t;
		for (int i = 1; i <= m; i ++) cin >> s[i];
		int ans = -1 + (b * (n - 1) <= t);
		for (int i = 1; i < m; i ++) {
			LL left = t - b * (s[i] - 1);
			int cnt = left < 0 ? 0 : min((LL)s[i + 1] - s[i], left / a + 1);
			ans += cnt;
			pos[i] = s[i] + cnt;
			gain[i] = get_gain(i);
		}
		for (int j = 1; j <= k - m; j ++) {
			int best = 1;
			for (int i = 2; i < m; i ++)
				if (gain[i] > gain[best]) best = i;
			if (!gain[best]) break;
			ans += gain[best];
			pos[best] += gain[best];
			gain[best] = get_gain(best);
		}
		cout << ans << "\n";
	}
	return 0;
}

7. 容易想到但不正确的方案

只按段长、剩余段长、从左到右或从右到左分配，都没有比较真实新增收益。先把初始收益排序、之后不更新，也忽略了同一段的收益会下降；多种顺序取最优仍不能代替正确的边际收益选择。

每段最多放一个或两个新增站也不成立。第一档总共只新增两站，因此“每段最多两个”在该档确实正确，应得到 $20$ 分；其他档会需要在同一段连续投入更多名额。

另外，答案是可达站点的数量，不是最远可达站号减一。样例中 $9$ 号站不可达而 $10$ 号站可达，已经说明可达车站不一定构成连续前缀。也不能坐过站后倒乘，因为题目只允许向编号增大的方向行驶。