【luogu P3403】跳楼机（图论）

跳楼机

题目链接：luogu P3403

题目大意

问你 1~h 中有多少个数可以表示成 ax+by+cz 的形式。
其中 x,y,z 是给出的三个正整数，a,b,c 是你可以选择的非负数。
h≤2^63-1，x,y,z≤10^5

思路

首先列出 $O(h)$ 的 DP 式子，但是显然不行，于是考虑优化。
有关 $h$ 的复杂度算法似乎没有什么进展，所以考虑另外三个范围小的数。

不妨思考如果只有两个数会怎样？
不难发现如果你确定了当前的数字，然后你只用一个数，那就是可以加上它的任意非负数倍数。
那如果你能凑出 $a$，你就不需要考虑 $a+x,a+2x,a+3x,...$ 这些数是否需要凑出了。

那某种意义上我们只需要考虑 $\min (x,y,z)$ 个数！
那假设我们用 $x$（因为三个都是同一个级别的），那我们只需要对于模 $x$ 等于 $0\sim x-1$ 的每个情况，我们求出这这些数中，你能求出的最小的数。
（也就是你能求出的是一段后缀，你要找到这段后缀开始的地方）

那怎么找呢？那我们只需要考虑用另外的两个数 $y,z$ 来凑。因为这个时候凑 $x$ 没有用了。
那我们可以从 $a$ 凑到 $(a+y)\%x,(a+z)\%x$，那就是一个 $f_{(a+y)\%x}=\min (f_{(a+y)\%x},f_a+y),f_{(a+z)\%x}=\min (f_{(a+z)\%x},f_a+z)$
那这个显然可能有环，但是由于是 $\min$ 我们其实会发现它其实可以看做一个最短路！

然后跑最短路就能求出 $f$，对于每个位置你计算一下后缀的长度，就是总共的答案了。

代码

#include
#include
#include
#define ll long long

using namespace std;

const int N = 1e5 + 100;
ll h, f[N];
int x, y, z;
priority_queue <pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > q;
bool in[N];

int main() {
	scanf("%lld", &h);
	scanf("%d %d %d", &x, &y, &z);
	
	memset(f, 0x7f, sizeof(f)); f[0] = 1; q.push(make_pair(f[0], 0));
	while (!q.empty()) {
		int now = q.top().second; q.pop();
		if (in[now]) continue; in[now] = 1;
		int to = (now + y) % x;
		if (f[to] > f[now] + y) {
			f[to] = f[now] + y; q.push(make_pair(f[to], to));
		}
		to = (now + z) % x;
		if (f[to] > f[now] + z) {
			f[to] = f[now] + z; q.push(make_pair(f[to], to));
		}
	}
	
	ll ans = 0;
	for (int i = 0; i < x; i++) {
		if (f[i] > h) continue;
		ans += (h - f[i]) / x + 1;
	}
	printf("%lld", ans);
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40