题解 [APIO2015]巴厘岛的雕塑
次阅读
2 min read
做过一道类似的题了(就是老板 dp 那道)……但再做这题还是做不出。
把 个数分成 组,使每一组的和或起来最小。
这种数位题,自然是从高位到低位 dp, 判断每一位是否可以为 , 然后就遇上了一个问题:不同位之间似乎是相关的啊,真的能直接去 dp 出来吗?
然后我就在这里卡壳了,来看题解的解决方法:
设置一个 res = ans | (1 << (i-1))
即设置一个 res
为把当前求出来的答案(由必须是 的)的当前位之后的都改成 , 然后设一段的和为 , 且 (s | res) == res
就可以令 。
显然不可能为了这一位是零而进行进位,因为这样子答案更大了,所以若当前的 不影响前面的位,且这一位是 可以做到,那就是可以转移的,反之就不行。
然而这一点我自己做的时候却总是想不到。
另外这题还提供了一个应对超时的新思路:极限数据若有特殊性质就给那特殊性质单独写一个(