题解

思路

记 $R_k=11\ldots1$ 为长度为 $k$ 的全一数。若表示中 $R_k$ 的净使用次数为整数 $x_k$，则

$$n=\sum_{k\ge1}x_kR_k,\qquad \text{cost}=\sum_{k\ge1}k|x_k|.$$

正负各一个相同长度的全一数可直接抵消，所以只需考虑净次数。

从低位到高位编号为 $0,1,\ldots$。令

$$a_i=\sum_{k>i}x_k,$$

即 $a_i$ 是所有长度超过 $i$ 的全一数在第 $i$ 位上的净系数。于是

$$n=\sum_{i\ge0}a_i10^i,qquad x_k=a_{k-1}-a_k.$$

这把原问题化为一个带进位的最短路。

做法

子任务一：整数图最短路

当 $n\le1000$ 时，把一定范围内的每个整数当作顶点。对于每个 $R_k$，从 $v$ 向 $v+R_k$ 和 $v-R_k$ 连边，边权为 $k$。从 $0$ 到 $n$ 的最短路就是答案。小范围内只需使用长度不超过 $5$ 的全一数，并保留足够大的正负值边界。

支线子任务：输入本身为全一数

若 $n=R_k$，直接使用它需要 $k$ 个 $1$。任何只使用不足 $k$ 个 $1$ 的表示，其绝对值都严格小于 $R_k$，因而答案恰为 $k$。

子任务三：显式活跃数量 DP

在某一位上，设仍覆盖这一位的正全一数有 $p$ 个，负全一数有 $q$ 个。向更高位移动时，$p,q$ 只能减小，因为某些数在当前位结束。若入进位为 $c$，则当前数位由 $c+p-q$ 对 $10$ 取模得到，同时产生新进位。每处理一位，代价增加 $p+q$。

对一类活跃数量做后缀最小值，对另一类显式枚举新数量，即可处理不超过八位的输入。

满分做法：系数差分与进位 DP

设 $d_i$ 为 $n$ 的第 $i$ 个十进制数位，$c_i$ 为进入该位的进位。数位等式为

$$a_i+c_i=d_i+10c_{i+1},$$

因此一旦知道相邻两个进位，就有

$$a_i=d_i+10c_{i+1}-c_i.$$

处理到第 $i$ 位时，状态只需保留 $(c_{i-1},c_i)$。枚举 $c_{i+1}$ 后，可以计算 $a_{i-1}$ 与 $a_i$，并加上

$$i|a_{i-1}-a_i|,$$

这正是长度为 $i$ 的全一数的贡献。在最高位后补一个零，最后将系数回归到零。

对任意五十位数，直接按相邻数位差构造表示，正、负活跃数量都不会超过 $225$。经过抵消规范化，最优解也可限制在该范围内，从而进位绝对值不超过 $28$。所以每层只需枚举 $57$ 种进位。

复杂度

设十进制位数为 $D$，进位状态数为常数 $C=57$。满分做法的时间复杂度为 $O(DC^3)$，空间复杂度为 $O(C^2)$。