题解

思路

从低位到高位处理加法。处理完低 $k$ 位后，某个 $B_i$ 是否向第 $k$ 位进位，只取决于已确定的 $A$ 的低 $k$ 位是否达到一个阈值。按 $B_i$ 的低 $k$ 位从大到小排序，所有发生进位的数必然组成这个顺序的一个前缀。因此状态只需记录进位数量 $j$。

在第 $k$ 位选择神器数字 $d$ 后，已知前 $j$ 个数带入进位，就能计算这一位全部输出数位的价格及下一位进位数。新顺序等于按当前 $B_i$ 数位从大到小稳定分桶，稳定性保留低位后缀顺序。

做法

算法一：枚举神器

小数据枚举所有问号替换，直接做大整数逐位加法并计算价格。

算法二：逐状态扫描

使用进位数量 DP。对每个位置、每个状态和每个可选数字扫描全部 $B_i$，直接求当前收益与新进位数，复杂度 $O(Ln^2\cdot10)$。

算法三：增量预处理

固定位置和数字 $d$，先计算没有输入进位时的总收益与输出进位数。把状态 $j$ 增加到 $j+1$ 只会改变稳定顺序中的一个 $B_i$，因此可在 $O(1)$ 内增量修改收益；只有 $b_{i,k}+d=9$ 时，输出进位数增加一。于是每个位置的全部转移只需 $O(10n)$。

最高处理到 $L=\max(|A|,\max|B_i|)$ 位。最后仍有进位的 $j$ 个数各多出一个最高位 $1$，只需额外加 $j c_1$，不能为其余数添加前导零价格。

正确性证明

对任意低位长度 $k$，进位条件为 $A_{<k}+B_{i,<k}\ge10^k$。因此按 $B_{i,<k}$ 降序排列后，进位集合是前缀。给定前缀长度 $j$ 与当前神器数位，所有当前输出数位和下一位进位均被唯一确定；按当前数位稳定分桶后，下一位进位集合仍是新顺序的前缀。DP 枚举题目允许的全部神器数位，故归纳得到每个状态的最大价格，最终再正确处理最高进位，答案最优。

复杂度

三档算法分别为问号枚举、$O(Ln^2\cdot10)$ 和 $O(Ln\cdot10)$ 时间；满分算法空间复杂度为 $O(Ln)$ 用于数位矩阵，DP 与顺序为 $O(n)$。