「POI2007」四进制天平 Quaternary Balance 题解

「POI2007」四进制天平 Quaternary Balance 题解

(n) 可以到 (10^{1000}) ，所以考虑数位 (dp)

当然这只是个直觉，具体怎么做呢？

砝码的质量都是 (4) 的幂，称出质量为 (m) 的物体，可以看成是一个 (4) 进制大整数的逐位确定，放左盘可理解为加法（该位为正），放右盘可理解为减法（该位为负），可以看出左右盘不可能都放。最后用的总砝码数等于各位数码的绝对值之和。

由于有负数，出现了前面放多，后面借位的可能，例子：

3  2  3  1
4  -1 0 -3

设 (S_{l,r}) 为 (n(base 4)) （n 为原数）中 ([l...r]) 一段拼接出的数。如果 (pos) 这一位多放了 (1) ，其实多的是 (4^{len-pos} - S_{pos+1,len})，那么后面为了借回来，就要用 (4^{len-pos})，为了平衡回来，后面就得变成 (4^{len-pos} - S_{pos+1,len}) 的四进制表示，再每位取相反数了。这等价于把 (pos + 1 ... len-1) 位减去 (3) ，最后一位减去 (4) 。

那么借位肯定是连续的一段。提前结束一段也有可能：

3  2  3  1
4  -2 3  1

结束一段后就恢复正常了。

我们再看看多段的情况：

1 *3  1  0 *2  2 *3  2
1  4  -2 -4 2  2  4  -2

不难发现，每段都是独立的，

那么可以设计出求最小砝码数的 (dp) ：(dp1_{i,j}) 表示考虑到第 (i) 位，这位是否在“一段”中。算好数码转移就好了，(O(len)) 的。

这题求的是方案数。要求还原方案的 (dp) 题写过吧？其实求方案数也一样，设一个 (dp2_{i,j}) ，算 (dp2) 时，只要 (dp1) 从这种方式转移过来是最优的，我们就可以累加。也是 (O(len)) 的。

所以这题数据似乎还可以加强...