题解 [APIO2007]动物园

感觉对这类在环上的状压问题很不熟悉(其实也不是环的原因),来记录一下心得。

其实,这不是一篇题解。

题面……难以概括。

这题的第一篇题解写的非常清楚,只是令我不太理解的是为什么这样的一个仅有 55 为状压的状态能代表最后的结果。

展示一下方程。

fi,S=max{fi1,(S&15)×2,f(S&15)×2+1}+num[i][S]f_{i,S} = \max\{f_{i-1, (S\&15) \times2}, f_{(S\& 15) \times 2 + 1}\} + num[i][S]

写出这个方程的精髓就在于,记录了当前之前的 若干个有用状态,并能从前面的状态继承答案,又能利于推出下面的状态。

意思是说,虽然只记录了五个东西的状态,但是记录的是到 ii 为止的答案,因为无后效性,使得这样子继承前面的答案并转移可以得到到当前这一位的答案,感觉很神奇的样子。

其实和 [NOI2001] 炮兵阵地 是同理的,只记录当前两行的状态,却能得到前 ii 行的答案,状压说白了就是将有后效性的部分状压掉放进状态里,使剩下的没有后效性。

另一个使我注意的地方在于,一类问题是形成环的,即开始的状态和结尾的状态时一模一样的。如这道题和 [SCOI2009]围豆豆。

处理这个问题的方法在这道题中表现为将除了初始状态的其它状态都设置为负无穷,并在最外层枚举起始/终结点,这是要求起始和结束状态完全一样的情况。

但在豆豆那题中,起始和结尾状态时可以不一样的,也可以一样,所以直接看做不同的点按照原来的 bfs 处理就可以了。