题解：P3403 跳楼机

lmlnl · 2024-08-31 13:52:10 · 题解

灵感来源于这篇文章。本题解介绍这篇文章中提到的同余最短路算法（下文简称转圈背包）。下文中的凑就是相加的意思，同时每个数可以无限使用。

我们先将所有可能使用的数构成的数列 w 排序，然后将第一个数 w_1 作为模数。接下来把问题分成两个部分处理。

2. 假设上一部分的值可以求出，那么如何计算总数呢？

先来解决第二部分。 设对于某个模数，最小值为 x，那么所有比他大且同余的数都可以凑出来。在 [l,r] 中与之同余且大于等于 x 的数的个数可表示为 f(r)-f(l - 1)，其中 f(a) 表示 [0,a] 中有多少个大于等于 x 的数。显然，这个函数可以按如下方式计算：

接下来，我们来解决第一部分，定义 dp_i 表示模 w_1 等于 i 的所有数中，最小的能凑成的数。这类似一个背包问题，但是会出现循环。对于每一个转移 w_i，会有 \gcd(w_1, w_i) 个循环。接下来，对于每个循环分别转移。

如果对于每个点都跑背包，复杂度有些过高了。所以我们发现，只需要转两圈来进行转移即可。这是因为，转两圈能让每个点之后转移到的点数都比圈长大，而这里又是模意义下的问题，所以这个优化是正确的。

第一部分复杂度 O(n \cdot \min(w_i))，第二部分复杂度 O(\min(w_i))，总体复杂度 O(n \cdot \min(w_i))。

这里给出一个参考代码：

#include<bits/stdc++.h>
using namespace std;
int w[5];
long long dp[1000010];
long long Gcd(long long x, long long y)
{
    if(y == 0) return x;
    return Gcd(y, x % y);
}
long long Calc(long long dis, long long x) {return (x >= dis) ? ((x - dis) / w[1] + 1) : 0;}
long long Circle(long long l, long long r, int n)
{
    for(int i = 2; i <= n; i++)
    {
        for(int fst = 0, lst = Gcd(w[1], w[i]) - 1; fst <= lst; fst++)
        {
            for(int cnt = 0, now = fst; cnt < 2; cnt += (now == fst))
            {
                int to = (now + w[i]) % w[1];
                dp[to] = min(dp[to], dp[now] + w[i]);
                now = to;
            }
        }
    }
    long long res = 0;
    for(int i = 0; i < w[1]; i++) res += Calc(dp[i], r) - Calc(dp[i], l - 1);
    return res; 
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n = 3;
    long long m;
    cin >> m;
    m--;
    for(int i = 1; i <= n; i++) cin >> w[i];
    sort(w + 1, w + n + 1);
    memset(dp, 0x3f, sizeof dp);
    dp[0] = 0;
    cout << Circle(0, m, n);
    return 0;
}