自动搬运

查看原文

来自洛谷，原作者为

	风羽跃 **

搬运于2025-08-24 21:33:34，当前版本为作者最后更新于2020-02-17 10:20:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本蒟蒻不才，实在想不出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;
}