同余最短路
|
阅读次
|
607 字
|
2 分钟

同余最短路

这是一个很有意思的算法，用于解决给定 n 个整数，求这 n 个整数能拼凑出多少的其他整数（n 个整数可以重复取）这一类问题，目的用于优化空间复杂度

例题

有 种硬币，面额 求能凑出 中，有多少价钱可被凑出。

暴力做法

考虑完全背包，但是 ，不可做

正解

我们用 来作为 这样，我们可以用 来表示 的任意一数
于是，我们对 的所有余数建图，即 0,1,2,3,4,5,6,7 共八个点
接下来我们建边

对于3

(0+3)%8=3 0 to 3
(1+3)%8=4 1 to 4
(2+3)%8=5 2 to 5
(3+3)%8=6 3 to 6
(4+3)%8=7 4 to 7
(5+3)%8=8 5 to 8
(6+3)%8=1 6 to 1
(7+3)%8=2 7 to 2

边权为3

对于7

(0+7)%8=7 0 to 7
(1+7)%8=0 1 to 0
(2+7)%8=1 2 to 1
(3+7)%8=2 3 to 2
(4+7)%8=3 4 to 3
(5+7)%8=4 5 to 4
(6+7)%8=5 6 to 5
(7+7)%8=6 7 to 6

边权为7

对于8

(0+8)%8=0
(1+8)%8=1
(2+8)%8=2
(3+8)%8=3
(4+8)%8=4
(5+8)%8=5
(6+8)%8=6
(7+8)%8=7

这种情况都是自环
边权为8

那么，我们得到了一个有向图，然后从0跑最短路，得到 dis[0~mod-1(7)] ，那么在 中，x的贡献与dis[x%mod(8)]相同
所以，每个余数(x)的贡献为 (m-dis[x])/mod+1。把所有余数贡献相加，便得到了答案

洛谷P3403 跳楼机

我们选xyz中的最小值作为mod，然后围绕这三个数进行同余最短路，最后再正常计数就行了，基本上是板子

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
41
42
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define ll long long
using namespace std;
ll dis[100005];
ll l[3];
queue < ll > q;
int main() {
    ll h;
    cin >> h;
    for (int i = 0; i < 3; i++) {
        cin >> l[i];
    }
    sort(l, l + 3);
    ll mod = l[0];
    memset(dis, 0x7f, sizeof(dis));
    dis[0] = 0;
    q.push(0);
    while (!q.empty()) {
        ll u = q.front();
        q.pop();
        for (int k = 1; k < 3; k++) {
            ll v = (u + l[k]) % mod;
            if (dis[u] + l[k] < dis[v]) {
                dis[v] = dis[u] + l[k];
                q.push(v);
            }
        }
    }
    ll ans = 0;
    for (int i = 0; i < mod; i++) {
        if (dis[i] <= h) {
            ans += (h - 1 - dis[i]) / mod + 1;
            //   if(dis[i]==0) ans--;// 排除地面（0层） 
        }

    }
    cout << ans;
    return 0;
}
上一篇
下一篇