这是本文档旧的修订版！
Educational Codeforces Round 104
F. Ones
题意
给定 $1\le n\lt 10^{50}$，要求用若干个形如 $11\cdots 11$ 的数以及加减号表示 $n$。求表达式中字符 $1$ 的个数的最小值。
题解 1
设 $\text{dp}(p,i,j,k)$ 表示最低 $p$ 位与 $n$ 相同，第 $p+1$ 位的进位为 $i$ (允许是负数)。
表达式中有 $j$ 个长度不小于 $p$ 的 $11\cdots 11$ 和 $k$ 个长度不小于 $p$ 的 $-11\cdots 11$ 的方案中仅统计所有数最低 $i$ 位的 $1$ 的个数的最小值。
记 $n$ 的第 $p$ 位为 $d$。当 $i+j-k\equiv d\bmod 10$ 时，有
$$ \text{dp}(p,\lfloor\frac {i+j-k}{10}\rfloor,j,k)\gets \min_{x\ge j,y\ge k}\text{dp}(p-1,i,x,y)+j+k $$
考虑二维前缀极值维护 $\min_{x\ge j,y\ge k}\text{dp}(p-1,i,x,y)$，于是可以 $O(1)$ 完成递推。
现在考虑状态数，首先 $j,k\le 5\ast\text{len}(n)$，因为可以用不超过 $5$ 个 $11\cdots 11$ 和不超过 $5$ 个 $-11\cdots 11$ 表示出 $n$ 的任意一位。
另外设 $i$ 上界为 $T$，于是 $|\frac {i+j-k}{10}|\le max\left(\left(|\frac {i+j}{10}|,|\frac {i-k}{10}|\right)\right)\le \frac {T+5n}{10}\le T$，故 $T\le \frac {5n}9$。
于是总状态数为 $O(n^4)$。滚动数组滚掉一维，时间复杂度 $O(n^4)$，空间复杂度 $O(n^3)$。
注意需要给 $n$ 补上一个前导 $0$，否则最高位无法借位，会遗漏形如 $9=11-1-1$ 的情况。
