p3464 sol（POI2007 WAG）

由于输入是 $10$ 进制的，考虑先将其转化为 $4$ 进制。位数不超过 $2000$。

由于进位与退位都是从高位往低位的，可以考虑从低往高 dp。设计状态 $f_{i,0/1}$ 表示考虑到从低往高第 $i$ 位，从第 $i+1$ 退了 $0/1$ 位。注意到进位一定不优，而退位不可能退 $2$ 位及以上，所以这个状态不会漏掉情况。

转移考虑从上一位递推，推推式子就好了。维护最小答案的同时还要维护方案数，建议用结构体重载运算符好写。