【DFS, 回溯】最大数字【蓝桥杯】

题目

最大数字 - 蓝桥云课

---

问题描述

给定一个正整数 $N$ 。你可以对 $N$ 的任意一位数字执行任意次以下 2 种操 作：

1. 将该位数字加 1 。如果该位数字已经是 9 , 加 1 之后变成 0 。

2. 将该位数字减 1 。如果该位数字已经是 0 , 减 1 之后变成 9 。

你现在总共可以执行 1 号操作不超过 $A$ 次, 2 号操作不超过 $B$ 次。 请问你最大可以将 $N$ 变成多少?

输入格式

第一行包含 3 个整数: $N, A, B$ 。

输出格式

一个整数代表答案。

样例输入

123 1 2

样例输出

933

样例说明

对百位数字执行 2 次 2 号操作, 对十位数字执行 1 次 1 号操作。

评测用例规模与约定

对于 $30 \%$ 的数据, $1 \leq N \leq 100 ; 0 \leq A, B \leq 10$ 。

对于 $100 \%$ 的数据, $1 \leq N \leq 10^{17} ; 0 \leq A, B \leq 100$

运行限制

• 最大运行时间：1s
• 最大运行内存: 512M

解题

方法一：DFS 回溯

思路

本题看起来像是从最高位开始的贪心，但其实是个暴搜题。

首先明确：要得到最优解，对于数字中的某一位必须要么做操作 $1$，要么做操作 $2$ ，而不能两种操作都做，因为操作 $1$ 与 $2$ 是相悖的，两种都做只会浪费次数。

接下来确定对于数中某一位有多少种情况，对于某一位来说：

1. 剩余的 $A$ 次数足以使它通过 $1$ 号操作加到 $9$ ；但剩余的 $B$ 次数不足以使它通过 $2$ 号操作减到 $9$ 。那就消耗 $A$ 次数把它加到 $9$ （把一位数变为 $9$ 是最优先操作）。
2. $A$ 次数不够；$B$ 次数够。那就消耗 $B$ 次数把它减到 $9$ 。
3. $A$ 次数够；$B$ 次数也够。那就分两个分支分别尝试 消耗 $A$ 次数把它加到 $9$ 和 消耗 $B$ 次数把它减到 $9$ 。
4. $A$ 次数不够；$B$ 次数也不够。此时只能消耗 $A$ 次数把该位加大。因为若使用 $B$ 也减不到 $0$ ，那么就只会减小该位，这是负贡献的！

接下来的暴搜就好写了：$dfs(i, inc, dec)$ （ $i$ 表示当前要操作第几位(从高位开始)，$inc$ 表示还剩多少次加操作，$dec$ 表示还剩多少次减操作 ）

• 出口：当枚举越界时 $i \ge n$ ，更新 $N$ 的最大值。
• 记录当前位上的数是 $d=num[i]$ ，那么要把它加到 $9$ 需要 $up=9-d$ 次，减到 $9$ 需要 $down=d+1$ 次；
  • 若 $inc \ge up$ 对应上面第 (1) / (3) 种情况，消耗 $up$ 次 $inc$ 把 $num[i]$ 加到 $9$ 。搜下一位： $dfs(i + 1, inc - up, dec)$ ，搜完后回溯（恢复当前位： $num[i] = d$ ）。
  • 若 $dec \ge down$ 对应上面第 (2) / (3) 种情况，消耗 $down$ 次 $dec$ 把 $num[i]$ 减到 $9$ 。搜下一位： $dfs(i + 1, inc, dec-down)$ ，搜完后回溯（恢复当前位： $num[i] = d$ ）。
  • 若 $inc < up \,\&\, dec < down$ 对应上面第 (4) 种情况，把 $inc$ 全部用完以把 $num[i]$ 加到 $num[i] + inc$ 。搜下一位： $dfs(i + 1, 0, dec)$ ，搜完后回溯（恢复当前位： $num[i] = d$ ）。

每一位的选择最多也就 $2$ 种，所以这么做的时间复杂度是 $O(2^{\log_{10}{N}})$ ，本题中 $100\%$ 的数据下最差时间复杂度是 $O(2^{17}) \approx O(10^5)$ 完全可以过。

代码

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

public class Main {
    static int n;
    static int[] num;
    static long ans = 0L;

    static void dfs(int i, int inc, int dec) {
        if (i == n) {
            long res = 0L;
            for (int x : num) res = res * 10 + x;
            ans = Math.max(res, ans);
            return;
        }
        int d = num[i], up = 9 - d, down = d + 1;
        if (inc >= up) {
            num[i] = 9;
            dfs(i + 1, inc - up, dec);
            num[i] = d;
        }
        if (dec >= down) {
            num[i] = 9;
            dfs(i + 1, inc, dec - down);
            num[i] = d;
        }
        if (inc < up && dec < down) {
            num[i] += inc;
            dfs(i + 1, 0, dec);
            num[i] = d;
        }
    }

    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        char[] s = in.next().toCharArray();
        n = s.length;
        num = new int[n];
        for (int i = 0; i < n; ++i) num[i] = s[i] - '0';
        int inc = in.nextInt(), dec = in.nextInt();
        dfs(0, inc, dec);
        System.out.println(ans);
    }
}