Luogu3403跳楼机

最短路

题面

给你三个数$x$,$y$,$z$，问你能够凑出多少个[1,$h$]之间的数。

解析

处理出$y$,$z$能凑出的高度
然后这些高度凑一些$x$就可以得到其它的高度
那么可以把这些$y$,$z$凑出的高度对$x$取模，其它的用$x$来填补
所以设$dp[i]$表示$y$,$z$凑出高度%$x$为$i$需要的最低高度
那么答案就是

代码

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=5e5;
int h[N],cnt,X,Y,Z;ll dp[N];
bool vis[N];
ll ans,H;
struct Edge{int to,next,w;}e[N<<1];
struct node
{
  ll dis;int u;
  bool operator < (const node &o) const {return dis>o.dis;}
};
priority_queue<node>Q;
il void add(re int u,re int v,re int w){e[++cnt]=(Edge){v,h[u],w};h[u]=cnt;}
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il void Dijstra()
{
  memset(dp,127,sizeof(dp));dp[1%X]=1;Q.push((node){1,1%X});
  while(!Q.empty())
    {
      re int u=Q.top().u;Q.pop();
      if(vis[u]) continue;vis[u]=1;
      for(re int i=h[u];i+1;i=e[i].next)
    {
      re int v=e[i].to;
      if(dp[v]>dp[u]+e[i].w)
        {
          dp[v]=dp[u]+e[i].w;
          Q.push((node){dp[v],v});
        }
    }
    }
}
int main()
{
  memset(h,-1,sizeof(h));
  H=gi();X=gi();Y=gi();Z=gi();
  if(Y<X) swap(Y,X);if(Z<X) swap(Z,X);
  fp(i,0,X-1) add(i,(i+Y)%X,Y),add(i,(i+Z)%X,Z);
  Dijstra();
  fp(i,0,X-1) if(dp[i]<=H) ans+=((H-dp[i])/X+1);
  printf("%lld\n",ans);
  return 0;
}