题解 P3403 【跳楼机】

· · 题解

回来复习,看见这道题博客还没写完,回来补了补;

这道题思路并不好想,说是同余,主要是因为统计答案时与跑最短路优化数组大小的方式罢了;

​ 先考虑如何统计答案,如果我们知道一个数 num 是由 y,z 构成的,即 num=a*y+b*z ,那么如果加上 x ,它能到达的楼层数为 (h-num)/x+1 其中 +1 是因为要统计不加 x 时的答案;

​ 那么如果我们能找到这些数,再去统计不就好了吗,但是会有重复,而且数字太过庞大,无法完全跑出,那么考虑什么时候回重复计数,即当 num1=num2+ax ,此时 num1 的贡献已经被 num2 统计过,再观察两个数字,发现 num1 \% x=num2 \% x ,那么我们只要找到余数相同中最小值即可,余数共有 x 种;

​ 设计转移方程: 设 f[i] 指余数为 i 时最小楼层数,那么转移有两种方式;

​ f[(i+y)\%x]=min(f[i]+y,f[(i+y)\%x])

​ f[(i+z)\%x]=min(f[i]+z,f[(i+y)\%x])

​ 我们可以用最短路来优化类似于点 i 与点 (i+y)\%x 连边,代价为 y ;

​ 讲到这应该就够了,这里附上的代码是我以前写的,有点丑,但是能看懂;

code

#include<bits/stdc++.h>
#define INF 1000000000000000LL
#define ll long long
#define maxn 100007
using namespace std;
ll h,dis[maxn];
int a[4],x,y,z,mn,vis[maxn];
int min(int x,int y){return x<y?x:y;}
queue<int >q;const int n=3;

void SPFA(){
    memset(dis,0x3f3f3f3f,sizeof(dis));
    vis[1]=1;q.push(1);dis[1]=1;
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=1;i<=n;i++) if(a[i]!=mn){
            int y=(a[i]+x)%mn;
            if(dis[y]>dis[x]+a[i]){
                dis[y]=dis[x]+a[i];
                if(!vis[y]) vis[y]=1,q.push(y);
            }
        }
        vis[x]=0;
    }
}

ll query(ll x){
    ll ans=0;
    for(int i=0;i<mn;i++){
        if(x>=dis[i]) ans+=(x-dis[i])/mn+1; 
    }
    return ans;
}

int main(){
//  freopen("srwudi.in","r",stdin);
//  freopen("srwudi.out","w",stdout);
    scanf("%lld%d%d%d",&h,&x,&y,&z);
    mn=min(x,min(y,z));
    if(x==1||y==1||z==1){
        printf("%lld",h);
        return 0;
    }
    a[1]=x,a[2]=y,a[3]=z;
    SPFA();
    printf("%lld",query(h));
    return 0;
}