p3464 sol（POI2007 WAG）

AllenJYL · 2024-12-19 08:06:07 · 题解

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

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

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