CF375C

__ryp__ · 2024-11-07 14:31:12 · 个人记录

我们设 f(x, y, S) 表示当前在 (x, y)，包含了的宝藏是 S，最少的移动步数。那么答案是 \max val_S - f(x, y, S)。

考虑转移。前两维的转移是简单的。由于转移顺序不确定，可以最短路。后面的 S 怎么动态维护？

计算几何中的射线法，可以用来判断某个点是否在某个多边形中。具体的方法是：从这个点做一条直线，看其经过这个多边形的多少条边。如果经过奇数条即是在内，否则在外。我们可以沿用相同的方法，每次转移时从每个宝藏平行向右做一条直线，看是否和新扩展出的点交。若交了，则其在 S 中取异或。

这样用最短路转移即可。