题目内容
给定两个整数 n,x
你可以对 x 进行任意次以下操作：
- 选择 x 的一位数字 y，将 x 替换为 x×y。
请你计算通过使用上述操作，将 x 变为一个 n 位数字（不含前导 00），所需要的最少操作次数。
例如，当 n=3,x=2 时，对 2 进行如下 4 次操作，即可使其变为 3 位数字：
- 将 2 替换为 2×2=4
- 将 4 替换为 4×4=16。
- 将 16 替换为 16×6=96
- 将 96 替换为 96×9=864
输入格式
共一行，包含两个整数 n,x
输出格式
一个整数，表示将 x 变为一个 n 位数字，所需要的最少操作次数。
如果无解，则输出 -1。
数据范围
所有测试点满足 2≤n≤19，1≤x<10^n-1
输入样例3：
13 42
输出样例3：
12
思路:这一题不能采用贪心的算法来求解,贪心的话13 42 的测试样例的结果是13，和正确结果不同。
因为可能每一次不乘x中最大的位数值。本题我们采用DFS（好剪枝），不采用(BFS)，如果采用BFS
有效的位数是2-9，0和1是无效的。有效的数是8个。如果采用BFS，时间复杂度就是8^n。所以我们
采用DFS,DFS可以有效剪枝.
本题的DFS有两处需要注意的地方
1.DFS遍历的数从高到低进行遍历,依次遍历9-2
2.剪枝，当 当前数据的操作数 + (n-当前数据的位数) >= 返回的位数值就直接return。因为 每次
操作最多能让当前数据的位数+1，n-当前的位数，能让我们大致推出当前数据到达n位大概还有几次
操作空间，加上当前数据的操作数就是总的操作数，总的操作数，如果比之前求的值大，就直接剪枝。
代码块
1 //BFS(剪枝)
2 #include <bits/stdc++.h>
3 using namespace std;
4 //INF表示的是遍历的最大次数
5 int n;
6 const int INF = 1000;
7 int ans = INF;
8 //x是传入的数值,res是x对应的操作数
9 void dfs(long long x, int d){
10 //表示x中出现的元素，后面DFS需要直到x中出现的元素值
11 bool st[10] = {0} ;
12 //获取x的位数
13 int cnt = 0;
14 for(long long y = x; y; y /= 10){
15 cnt++;
16 //表示x中 xx % 10 的数值有在位数中出现过
17 st[y%10] = true;
18 }
19 //剪枝，如果当前的操作数 + (元素的位数(n) - 元素当前的位数(cnt) ) >= ans 的话，就可以不用遍历了
20 if(d + n - cnt >= ans) return ;
21 //如果当前的位数和n相同，改变ans的值
22 if(cnt == n){
23 ans = d;
24 return;
25 }
26 //DFS，DFS从大的数值往小的数值进行遍历
27 for(int i = 9; i >= 2; i--){
28 //如果该数在x的位数的数值中有出现就遍历
29 if(st[i])
30 dfs(x*i,d+1);
31 }
32 }
33 int main() {
34 long long x;
35 cin >> n >> x;
36 dfs(x,0);
37 //如果无解，将rr变成-1
38 if(ans == INF) ans = -1;
39 cout << ans << endl;
40 return 0;
41 }
题目来源 4868. 数字替换 - AcWing题库
题解思路来源个人空间 - AcWing