题解 | 1=N 一种简单的DP做法

考虑 $f[x]$ 是代表到达 $x$ 的最小成本，显然初始化 $f[1]=0$ ，答案是 $f[n]$

状态转移方程：

$f[x]=\max(f[x],f[v]+\dfrac x v)$

其中 $v$ 是 $x$ 的因子，例如 $f[8]$ 可以由 $f[4]$ 加上费用 $\dfrac 8 4=2,(4\times 2=8)$ 得到。

如果直接每次都枚举每个数再判断是否是因子的话，时间复杂度是 $O(n\sqrt n)$ 的，容易超标，考虑先枚举每个数的约数集合进行预处理，这个操作的时间复杂度是 $O(n\log n )$ 的，然后存入数组中进行DP，这样获取因子的时间复杂度就是 $O(1)$ 了，而且 $3\times 10^5$ 以内因子数量最多的不超过200个，所以时间复杂度可以稳稳通过本题，代码如下：

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define erp(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int N=3e5+7;
int n;
vector<int> g[N];
int f[N];
void solve(){
	cin>>n;
	int b=sqrt(n)+10;
	rep(i,1,b){
		rep(j,1,n/i){
			g[i*j].push_back(i);
			if(i!=j)g[i*j].push_back(j);
		}
	}
	f[1]=0;
	rep(i,2,n){
		f[i]=0x3f3f3f3f;
		for(auto& v:g[i]){
			f[i]=min(f[i],f[v]+(i/v));
		}
	}
	cout<<f[n];
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	int tt=1;
	while(tt--)solve();
	return 0;
	
}

后面发现这样做其实是写蠢了，既然枚举因子的时候可以直接获取他的倍数，那干脆dp的时候就从因子开始dp了，当前的因子的dp值直接决策后续的dp值，然后初始化每个f[i]=i即可，这样做的时间复杂度是 $O(n\log n)$ 的。

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define erp(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int N=3e5+7;
int n;
int f[N];
void solve(){
	cin>>n;
	f[1]=0;
	f[2]=2;
	rep(i,3,n)f[i]=i;
	rep(i,2,n)rep(j,2,n/i)f[i*j]=min(f[i*j],f[i]+j);
	cout<<f[n];
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	int tt=1;
	while(tt--)solve();
	return 0;
}