// 同余最短路 Dijkstra 算法 O(MlogN)
#include<bits/stdc++.h>
#define ll long long
#define pli pair<ll,int>
using namespace std;

const int N=100010,M=N*2;
const ll inf=(1ull<<63)-1; //long long 的最大值
ll h[M],idx,to[M],ne[M],ww[M];
void add(ll u,ll v,ll w){
  to[++idx]=v;ww[idx]=w;ne[idx]=h[u];h[u]=idx;
}
ll H,x,y,z;
ll d[N],vis[N];

void dijkstra(){
  for(int i=0;i<x;i++) d[i]=inf; d[0]=0;
  priority_queue<pli,vector<pli>,greater<pli> > q; 
  q.push({0,0});
  
  while(!q.empty()){
    int u=q.top().second; q.pop();
    if(vis[u]) continue; vis[u]=1;
    for(int i=h[u]; i; i=ne[i]){
      int v=to[i],w=ww[i];
      if(d[v]>d[u]+w){
        d[v]=d[u]+w;
        q.push({d[v],v});
      }
    }
  }
}
int main(){
  cin>>H>>x>>y>>z;
  for(int i=0; i<x; i++){
    add(i,(i+y)%x,y);
    add(i,(i+z)%x,z);
  }
  
  dijkstra();
  ll ans=0; --H;
  for(int i=0;i<x;i++)
    if(H>=d[i]) ans+=(H-d[i])/x+1;
  cout<<ans<<'\n';
}

依旧是不看题解的一天。

好像 zyx 跟我说过这道题，当时好像没想出来。现在发现还是太简单了。

三个数跑肯定爆了，那就简化成在模 $a$ 为 $i$ 的情况下能抵达的最低楼层。

然后写队列，用堆优化（其实就是 dijkstra）。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10,inf=((1ll<<62)-1)*2+1;
#define PII pair<int,int>
#define fi first
#define se second
int a,b,c,d[N],v[N];
void dij()
{
	priority_queue<PII,vector<PII>,greater<PII>>q;
	for(int i=1;i<=a;i++)d[i]=inf;
	q.push({0,1});d[1]=1;
	while(!q.empty())
	{
		int x=q.top().se;q.pop();
		if(v[x])continue;v[x]=1;
		int x1=(x+b)%a;if(x1==0)x1+=a;
		if(d[x1]>d[x]+b)
			d[x1]=d[x]+b,q.push({d[x1],x1});
		int x2=(x+c)%a;if(x2==0)x2+=a;
		if(d[x2]>d[x]+c)
			d[x2]=d[x]+c,q.push({d[x2],x2});
	}
}
signed main()
{
	int n;cin>>n>>a>>b>>c;
	if(b>c)swap(b,c);if(a>b)swap(a,b);
	dij();
	int ans=n;
	for(int i=1;i<=a;i++)
	{
		if(d[i]<=n)
			ans-=(d[i]-i)/a;
		else
			ans-=(n/a+(i<=(n%a)));
	}
	cout<<ans;
	return 0;
}