P2064题解

金霸王电池 · 2022-03-05 15:09:48 · 题解

为什么我只会用 DFS 做这道题啊

观察发现，每一天行驶的路程都是 a 的倍数，那么 a 就是 S 的约数。列出 S 的所有约数（n 除外，因为至少开两天的车），枚举 a，S 再除以 a。至此，问题转化为：第一天行驶一公里，后面每一天行驶的路程是到前一天的 2~9 倍，求最快几天到达。

对于这个问题，考虑 DFS 。设 dfs(n) 表示行驶 n 公里至少多少天，则 dfs(n)=\min_{2\leq i\leq 9}dfs(\frac{n}{i})。

边界条件：dfs(1)=1。

AC 代码：

#include<bits/stdc++.h>
using namespace std;
int s,a[1000000],top,minn=1e8;
int dfs(int t){//搜索
    if(t==1)return 1;//边界条件
    int k=t-1,minx=1e8;
    for(int i=2;i<=9;i++)
        if(k%i==0)
            if(dfs(k/i)!=-1)minx=min(minx,dfs(k/i)+1);//取 min
    if(minx==1e8)return -1;//到达不了
    return minx;
}
int main(){
    cin>>s;
    for(int i=1;i<=sqrt(s);i++)
        if(s%i==0){
            top++;
            a[top]=i;
        }//所有因子
    for(int i=2;i<=top;i++)a[2*top+1-i]=s/a[i];
    top=top*2-1;
    for(int i=1;i<=top;i++){
        s/=a[i];
        if(dfs(s)!=-1)minn=min(minn,dfs(s));//依次枚举
        s*=a[i];
    }
    if(minn==1e8)cout<<-1;//到达不了
    else cout<<minn;
    return 0;
}