【DFS, 剪枝】数字替换

题目

4868. 数字替换 - AcWing题库

---

给定两个整数 $n,x$ 。

你可以对 $x$ 进行任意次以下操作：

• 选择 $x$ 的一位数字 $y$ ，将 $x$ 替换为 $x \times y$ 。

请你计算通过使用上述操作，将 $x$ 变为一个 $n$ 位数字（不含前导 $0$ ），所需要的最少操作次数。

例如，当 $n=3,x=2$ 时，对 $2$ 进行如下 $4$ 次操作，即可使其变为 $3$ 位数字：

1. 将 $2$ 替换为 $2 \times 2 = 4$ 。
2. 将 $4$ 替换为 $4 \times 4 = 16$ 。
3. 将 $16$ 替换为 $16 \times 6 = 96$ 。
4. 将 $96$ 替换为 $96 \times 9 = 864$ 。

输入格式

共一行，包含两个整数 $n,x$ 。

输出格式

一个整数，表示将 $x$ 变为一个 $n$ 位数字，所需要的最少操作次数。

如果无解，则输出 -1。

数据范围

所有测试点满足 $2 \le n \le 19$ ， $1 \le x < 10^{n-1}$ 。

输入样例1：

2 1

输出样例1：

-1

输入样例2：

3 2

输出样例2：

4

输入样例3：

13 42

输出样例3：

12

解题

方法一：DFS 剪枝

思路

本题中 $x$ 最大有 $18$ 位数，肯定会爆 int ，所以用 long 来存，而最多需要该数变为 $19$ 位，也就是说该数最大会变为 $999999999999999999 \times 9 = 8999999999999999991 \approx 9\times 10^{19} \le 2^{63} - 1 (\approx 9.2 \times 10^{19})$ 不会爆 long ，刚刚好能存下。

暴搜：$dfs(x, step)$（ $x$ 表示当前数字， $step$ 表示当前已进行了多少步操作 ）

• 枚举 $x$ 的每一位并计数。
• 出口：当 $x$ 的位数等于 $n$ 时，已达到要求，更新最少操作步数，退出。
• 枚举 $x$ 所有位上有的数字，递归下一步操作 $dfs(x \times d, step + 1)$ 。

剪枝：

1. 优化搜索顺序：$x$ 乘以越大的数越容易使 $x$ 的位数增加，所以枚举位数的时候应按照 $9 \to 2$ 的顺序来枚举。
2. 最优性剪枝：如果 操作步数 $+$ 距离目标相差的位数 $\ge$ 最少操作步数，就应该直接剪枝。

注意：本题时间复杂度比较极限，且输入数字大过 $10^{14}$ ，所以使用StringTokenizer输入。

代码

import java.util.*;
import java.io.*;

public class Main {
    static final int INF = 100;
    static int n, ans = INF;
    
    static void dfs(long x, int step) {
        boolean[] has = new boolean[10];
        int cnt = 0;
        for (long t = x; t > 0; t /= 10) {
            has[(int) (t % 10)] = true;
            ++cnt;
        }
        if (step + n - cnt >= ans) return;
        if (cnt == n) {
            ans = step;
            return;
        }
        for (int d = 9; d >= 2; --d) {
            if (has[d]) dfs(x * d, step + 1);
        }
    }
    
    public static void main(String[] args) {
        Kattio io = new Kattio();
        n = io.nextInt();
        long x = io.nextLong();
        dfs(x, 0);
        io.println(ans == INF ? -1 : ans);
        io.flush();
    }

    static class Kattio extends PrintWriter {
        private BufferedReader r;
        private StringTokenizer st;
        public Kattio() { this(System.in, System.out); }
        public Kattio(InputStream i, OutputStream o) {
            super(o);
            r = new BufferedReader(new InputStreamReader(i));
        }
        public Kattio(String intput, String output) throws IOException {
            super(output);
            r = new BufferedReader(new FileReader(intput));
        }
        public String next() {
            try {
                while (st == null || !st.hasMoreTokens())
                    st = new StringTokenizer(r.readLine());
                return st.nextToken();
            } catch (Exception e) { }
            return null;
        }
        public int nextInt() { return Integer.parseInt(next()); }
        public double nextDouble() { return Double.parseDouble(next()); }
        public long nextLong() { return Long.parseLong(next()); }
    }
}