题解 P3403 【跳楼机】

· · 题解

题解（瞎吹）

如果不考虑h的大小问题，那么我们可以得到一个简单的dp:

f(i)=f(i-x)|| f(i-y)|| f(i-z) f(1)=true

因为h过大，这个dp的时空复杂度过高，不能接受，因此需要进行优化。

最终上升到的楼层和操作的顺序没有关系，所以我们可以将一种操作堆积起来，将一个到达的楼层分解为:

h=ax+by+cz

首先我们用最短路的方式求出数组f()，不知道怎么计算的到时候看代码

f(i)=\min\limits_h\{h\mod z=i\}

其中h=ax+by

翻译成人话就是用前两种操作到达一个高度h，这个高度和z取模的结果是i，f(i)表示的是最小的h。

求出这个f()之后，我们从楼层f(i)出发，只用操作3能够到达的楼层有\lfloor{h-f(i)\over x}\rfloor + 1 \ \ \ (1)

那么这个答案是否有遗漏呢，假设我们从f(i)出发，用操作1，2再走到了一个楼层h'，这个楼层依然满足h'\mod z=i，那么可以得到:

h'=\lfloor{h'\over z}\rfloor z+i \because h=\lfloor{h\over z}\rfloor z+i \therefore h'-h=(\lfloor{h'\over z}\rfloor-\lfloor{h\over z}\rfloor)z

所以这个楼层h'其实也可以由h使用几次操作3得到，也就说它会被计算到式子(1)中，不会被遗漏，那么我们最终的答案可以表示为:

ans = \sum\limits_{i=0}^n \lfloor{h-f(i)\over x}\rfloor+1

这样的计算是不会用重复的。简单的证明（乱搞）如下：

使用反证法，如果同一个楼层能使用两种不同的方式得到，如果a_1 \neq a_2, b_1\neq b_2, c_1\neq c_2，那么:

a_1x+b_1y+c_1z=a_2x+b_2y+c_2z=h

两个多项式相等，则这两多项式最高次数相同，且对应次数项的系数相同.

那么得到

a_1=a_2,b_1=b_2,c_1=c_2

显然两个方法其实是同一个。

如果a,b,c有两个是相等的，那么就可以将这两个相等字母所在的单项式合并，依然是类似于上面的结果。

#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int maxn = 1e5 + 5;
struct Edge {
    int v, nex; LL w;
    Edge(int v = 0, LL w = 0, int nex = 0) : v(v), w(w), nex(nex) {}
} E[maxn << 2];

int head[maxn], tote;
void addEdge(int u, int v, LL w) {
    E[++tote] = Edge(v, w, head[u]), head[u] = tote;
} 
LL h, x, y, z;
bool vis[maxn];
LL f[maxn];
queue<int> q;

int main() {
    memset(f, 0x3f, sizeof(f));
    memset(head, -1, sizeof(head));
    // freopen("testdata.in", "r", stdin);
    // freopen("testdata.out", "w", stdout);
    scanf("%lld%lld%lld%lld", &h, &x, &y, &z);
    for (int i = 0; i < x; i++) 
        addEdge(i, (i + y) % x, y),
        addEdge(i, (i + z) % x, z);
    q.push(1 % x), f[1 % x] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop(), vis[u] = false;
        for (int i = head[u]; ~i; i = E[i].nex) {
            int v = E[i].v;
            if (f[v] > f[u] + E[i].w) {
                f[v] = f[u] + E[i].w;
                if (!vis[v]) vis[v] = true, q.push(v);
            }
        }
    }
    LL ans = 0;
    for (int i = 0; i < x; i++)
        if (f[i] <= h) ans += (h - f[i]) / x + 1;
    printf("%lld\n", ans);
    return 0;
}