题解 P2064 【奇妙的汽车】

· · 题解

本蒟蒻不才，实在想不出dp，就来推一下这道题的式子：

设我们第一天跑了a，第二天是第一天的k1倍，第三天是第二天的k2倍……以此类推。

那我们就以4天为例，推一下式子：

总路程 s = a + k1a + k2k1a + k3k2k1a 

       = a(1 + k1 + k2k1 + k3k2k1 )

       = a(1 + k1(1 + k2 + k3k2))

       = a(1 + k1(1 + k2(1 + k3)))

恍然大悟，那我们就可以先把 a 约掉，再递归求出 k1,k2,k3……的值。

然后我们可以发现，总路程 s 一定能被 a 整除。

所以就用试除法求出 s 的所有因数，每个因数都做一遍dfs，求一个最小值就行了！

但是题目中有一个要求：不能1天到达。

那样的话判断一下a不等于n就行了！

AC代码加注释：

#include<cstdio>
#include<iostream>
#include<cmath>

#define INF 0x7fffffff

using namespace std;

int n,ans=INF;

inline void dfs(int dep,int num)
{
    if(!num){
        //边界条件
        ans=min(ans,dep);
        return ;
    }
    num--;//把式子里面的1减掉
    for(int i=2;i<=9;i++){//枚举k
        if(!(num%i)){//判断整除
            dfs(dep+1,num/i);
        }
    }
}

int main()
{
    cin>>n;
    for(int i=1;i<=sqrt(n);i++){
        //因数一定是成对出现，所以我们枚举的a实际上是i和n/i
        if(!(n%i)){判断整除
            if(n/i!=n) dfs(0,i);//n/(n/i)=i
            if(i!=n) dfs(0,n/i);//n/i
        }
    }
    if(ans!=INF) cout<<ans<<endl;//判断能否到达
    else cout<<-1<<endl;
    return 0;
}