https://zybuluo.com/ysner/note/1099616
题面
给你三个数(x),(y),(z)，问你能够凑出多少个[1,(h)]之间的数。
解析
处理出(y),(z)能凑出的高度
然后这些高度凑一些(x)就可以得到其它的高度
那么可以把这些(y),(z)凑出的高度对(x)取模，其它的用(x)来填补
所以设(dp[i])表示(y),(z)凑出高度%(x)为(i)需要的最低高度
那么答案就是$$ans=sum_{i=0}^{x-1}（frac{h-dp[i]}{x}+1）$$
代码
#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
",ans);
return 0;
}