题解 P3403 【跳楼机】

· · 题解

难点主要在于思维的转化

令f(i)表示表示仅通过操作2和操作3能到达的 mod x = i 的最小楼层

很容易得出状态转移方程

能到达mod x=i+y的最小楼层
即,在能到达mod x=i的最小楼层的基础上,再执行一遍操作2

那么有了状态转移方程,如何快速地求出来呢?

我们来看看最短路的求法

这个写法跟我们上面的转移方程很像诶 于是考虑让$(i+y)$和$(i+z)$成为点; 让$y,z$成为权值从而算出$f(i)$; ### 算出$f(i)$有什么用呢? $ans+=(h-f[i])/x +1$; 由于$f(i)$是在不适用操作$1$的情况下 所以$h$和$f(i)$之间的差值由操作$1$来完成 而每进行操一次作$1$,我们就可以到达一个新的楼层 所以答案就要累加上进行操作$1$的次数 #### 即 $(h-f[i])/x +1

为什么要+1呢,
因为除法是向下取整,注意由于f数组的存在,是不可能出现刚好被整除的,这一点请自己思考

Code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>

using namespace std;

const int N=1e5+3;
const int INF=0x3f3f3f3f;

long long h,x,y,z;
long long f[N],ans;
bool vis[N];
int tot,ver[N*2],Next[N*2],edge[N*2],head[N];

/*f(i)表示仅通过2操作和3操作能到达的 mod x = i 的最小楼层 
显然
    f(i+y)=f(i)+y
    f(i+z)=f(i)+z;
而最短路的求法
    f(y)=f(x)+edge(i);
让(i+y)和(i+z)成为点
让y,z成为权值
从而算出f(i) 
*/
void add(int x,int y,int z)
{
    ver[++tot]=y;
    Next[tot]=head[x];
    head[x]=tot;
    edge[tot]=z;
}

void spfa()
{
    memset(f,INF,sizeof(f));
    memset(vis,0,sizeof(vis));
    queue<int> qwq;
    qwq.push(1);
    vis[1]=1;
    f[1]=1;
    while(!qwq.empty())
    {
        int x=qwq.front();qwq.pop();
        vis[x]=0;
        for(int i=head[x];i;i=Next[i])
        {
            int y=ver[i];
            if(f[y]>f[x]+edge[i])
            {
                f[y]=f[x]+edge[i];
                if(!vis[y])
                {
                    qwq.push(y);
                    vis[y]=1;
                 } 
            }
        }
    }
}

int main()
{
    scanf("%lld\n%lld%lld%lld",&h,&x,&y,&z);
    if(x==1 || y==1 || z==1){cout<<h;return 0;} //特判 
    for(int i=0;i<x;i++)
    {
        //关键点 
        add(i,(i+y)%x,y);
        add(i,(i+z)%x,z);
    }
    spfa();
    for(int i=0;i<x;i++)
        if(f[i]<=h)
            ans+=(h-f[i])/x +1;
            //显然 

    printf("%lld",ans);

    return 0;
}