考虑令 \(l = |n|\)，最高位为第 \(1\) 位，最低位为第 \(l\) 位。
考虑选了一个 \(\pm\underbrace{11\cdots11}_{i}\)，那么显然会对 \(l - i + 1\sim l\) 位都有影响。
于是能够知道第 \(i\) 位只有可能由 \(< i\) 的位影响。
便可以考虑由高位到低位依次考虑，假设到了第 \(i\) 位。
首先需要考虑 \(\le i\) 的位已经给第 \(i\) 位加了多少了。
同时考虑到 \(< i\) 的位可能给第 \(i\) 位留下了一些空去补。
同时考虑记录一下第 \(i\) 位选择 \(+ 1\) 还是 \(- 1\)，显然不会又有 \(+1\) 又有 \(-1\)。
所以可以设 \(f_{i, x, c, \Delta}\) 分别代表上面的量对应的值所需要的最小花费。
考虑会有 \(2\) 种选择：
- 第 \(i\) 位 \(+ \Delta\)，花费 \(1\)，直接在 \(x\) 的部分 \(+ \Delta\) 即可。
\(f_{i, x + \Delta, c, \Delta} + l - i + 1\to f_{i, x, c, \Delta}\)。 - 推到第 \(i + 1\) 位，那么第 \(i + 1\) 位就可能是 \(1\) 或 \(-1\)，同时可以更新 \(c\)，相当于前面的差值后面添上了这位的差值，就是 \(10c + s_i - \Delta\)。
\(\min\{f_{i + 1, x, 10c + s_i - x, -1 / 1}\}\to f_{i, x, c, \Delta}\)。
边界条件就是当 \(i = l\) 的时候，要求到 \(i + 1\) 的时候 \(c = 0\) 才是合法的，相当于就是要使 \(10c + s_l - x' = 0\) 的 \(|x - x'|\) 的这个值，所以有 \(f_{l, x, c, ?} = |10c + s_l - x|\)。
但这个 \(c, x\) 的范围都会很大，但是考虑到大部分状态都是没用的，考虑减掉这部分状态。
首先考虑 \(x\)。
考虑到 \(\underbrace{77\cdots77}_{i} = \underbrace{11\cdots11}_{i + 1} - \underbrace{33\cdots3}_i - 1\)，先把这个 \(-1\) 考虑到第 \(l\) 位已经特殊处理了，那么就可以知道实际上对于第 \(i\) 位来说不会操作 \(> 6\) 次。
那么一共有 \(l\) 位，操作次数就会 \(\le 6l\)，于是有 \(x\le 6l\)。
再考虑 \(c\)，考虑若 \(c \ge 0\)，最后 \(c\) 肯定还是要满足最小值 \(\le 0\) 才有可能为 \(0\)。
考虑对于第 \(l\) 位的 \(c\)，那肯定有 \(10c - x\le 0\)。
继续，有 \(10(10c - x) - x\le 0\)，到了最后会成这样：\(c\le \dfrac{\underbrace{11\cdots11}_{l} x}{10^l}\)。
卡一个宽松的上界，肯定有 \(c\le \frac{x}{5}\)。
然后直接 \(\text{DP}\) 就行了。
时间复杂度 \(O(n^3)\)。
代码
#include<bits/stdc++.h>
const int inf = 0x3f3f3f3f;
const int maxl = 50 + 2, maxx = maxl * 6, maxc = maxx / 5;
char S[maxl];
int s[maxl];
int l, mxx, mxc;
int f[maxl][maxx << 1][maxc << 1][3];
int dfs(int w, int x, int c, int v) {
if (w == l)
return abs((c * 10 + s[w]) - x);
if (x < -mxx || x > mxx || c < -mxc || c > mxc)
return inf;
int &ans = f[w][mxx + x][mxc + c][v + 1];
if (ans == -1)
ans = std::min({dfs(w, x + v, c, v) + l - w + 1,
dfs(w + 1, x, c * 10 + s[w] - x, 1),
dfs(w + 1, x, c * 10 + s[w] - x, -1)});
return ans;
}
int main() {
scanf("%s", S + 1);
l = strlen(S + 1);
for (int i = 1; i <= l; i++)
s[i] = S[i] - '0';
mxx = l * 6, mxc = mxx / 5;
memset(f, -1, sizeof(f));
printf("%d\n", dfs(0, 0, 0, 1));
return 0;
}