题解 P2566 【[SCOI2009]围豆豆】

2019-01-05 15:42:25


对下面的一句话题解/部分题解表示强烈谴责qwq 我这种小菜鸡都看不懂qwq

所以还是自己写一篇,希望能让大家都看懂qwq


这题思路好神仙啊qwq

前置知识

如何判断一个点是否在一个多边形内部?从这个点向外引一条射线,若与多边形相交了奇数次,就在它的内部,否则在外部。

正解

$d$ 很小,考虑状压DP。

预处理出豆子的坐标和每个状态 $S$ 下所有豆子的得分和 $sum[S]$ 。

首先枚举一个起点 $(x,y)$ 。设 $f[i][j][S]$ 表示走到了 $(i,j)$ 这个格子,当前圈住的豆子的状态为 $S$ 的最小边界长度。显然这个东西可以跑一遍最短路得到,具体实现还是见代码qwq。

然后,枚举状态 $S$ 。因为要走一条回路,所以用 $sum[S]-f[x][y][S]$ 来更新答案。

最后输出答案,然后就做完啦。

代码见blog