题目背景 DJL 为了避免成为一只咸鱼，来找 srwudi 学习压代码的技巧。 问题描述 Srwudi 的家是一幢 h 层的摩天大楼。由于前来学习的蒟蒻越来越多，srwudi 改造了一 个跳楼机，使得访客可以更方便的上楼。 经过改造，srwudi 的跳楼机可以采用以下四种方式移动： 1. 向上移动 层； x 2. 向上移动 y 层； 3. 向上移动 z 层； 4. 回到第一层。 一个月黑风高的大中午，DJL 来到了 srwudi 的家，现在他在 srwudi 家的第一层，碰巧 跳楼机也在第一层。DJL 想知道，他可以乘坐跳楼机前往的楼层数。 输入格式 第一行一个整数 h，表示摩天大楼的层数。 第二行三个正整数，分别表示题目中的 x, y, z。 输出格式 一行一个整数，表示 DJL 可以到达的楼层数。 样例输入 15 4 7 9 样例输出 9 样例解释 可以到达的楼层有：1,5,8,9,10,12,13,14,15 数据范围 对于 20%的数据， ≤h, x, y, z≤100； 对于 40%的数据，1≤h, x, y, z≤10的5次方   对于 100%的数据，1≤h≤10的18次方，1≤x, y, z≤10 的5次方   解题思路 1 直接bfs 状态太多 我们考虑减少状态 记di=c, 表示在满足c mod x==i 的前提下 仅通过第二和第三个操作可以到达的最小楼层 c 如果我们得到了 d ， 那么最后的答案就是       对于di的计算 我们有如下两种形式的转移  d(i+y) mod x = di +y d(i+x) mod x = di + z 因为你求的 是di 的min 不难发现 这就是最短路模型 可以使用SPFA 2 首先可以先写出 h=ax+by+cz； 然后再看题 可以 大致猜出 在到达这个楼层hi 之前 你是怎么到达的 不管 也就是说 你可以先跳完 y z 再跳 x 那么你就可以 把 h %x h'=by+cz; h=h'+k*x; 这时因为每次加的都是整数倍的x 那么 你可以求每次h' %x ==i 记录 di 为mod x 的最小能够到达的楼层  也就是说d(i+y)mod x = di +y              d(i+z) mod z  = di+z;     问题1 为啥只用算一边   因为你算的是当前x 对答案的贡献  而每次到达di 是上一个状态加1 通过操作2 3到达的 而上一个到达的楼层 是 di-y 或 di-z 且mod x不等于 di 的 i 不然还算什么啊  所以要加1     其他优秀题解     如果不考虑h的大小问题，那么我们可以得到一个简单的dp: 背包 

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

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

h=ax+by+cz

 

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

 

 

所以没有遗漏

 

code

//
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define inf (1ll<<62)
ll dis[200005],x,y,z;
ll h;
queue <int > Q;
int mark[200005];
void spfa()
{
    for(int i=0;i<=x;i++) dis[i]=inf;
    dis[1%x]=1;
    Q.push(1%x);
    mark[1%x]=1;
    while(Q.size())
    {
        int s=Q.front();
        mark[s]=0;
        Q.pop();
        if(dis[(s+y)%x]>dis[s]+y)
        {
            dis[(s+y)%x]=dis[s]+y;
            if(!mark[(s+y)%x])
            {
                Q.push((s+y)%x);
                mark[(s+y)%x]=1;
            }
        }
            if(dis[(s+z)%x]>dis[s]+z)
        {
            dis[(s+z)%x]=dis[s]+z;
            if(!mark[(s+z)%x])
            {
                Q.push((s+z)%x);
                mark[(s+z)%x]=1;
            }
        }
    }
    
}
int main()
{
    cin>>h;
    cin>>x>>y>>z;
    spfa();
    ll ans=0;
    for(int i=0;i<x;i++)
    {
        if(dis[i]<=h&&dis[i]!=inf)
        ans+=(h-dis[i])/x+1;
    }
    printf("%lld",ans);
}