FencingPenguins

作者：丁力煌

关键词：动态规划 计算几何

题目描述

平面上有中心在原点，一个点在(r,0)处的正n边形的n个顶点。平面上还有m个企鹅，每个企鹅有一个位置和一个颜色，现在要连一些边，使得每个点的度数都是0或2，这样会构成若干个顶点不相交的圈，求满足以下条件的连边方案数：

1、每个圈里有至少一个企鹅；

2、任意两个圈不相交；

3、每种颜色的企鹅在同一个有限区域中；

4、每个企鹅在一个有限区域内；

$n\leq222,m\leq50,r\leq10^5$,
企鹅的颜色保证是大写字母或者小写字母，坐标范围$\leq10^5$,企鹅离任一条n个点连的边的距离$\geq 10^{-6}$

算法

首先，显然如果有企鹅在一个连边是符合条件3的当且仅当对于每条边，每种颜色的企鹅都在这条直线的同一侧。所以可以预处理出哪些直线是符合这个条件的，时间复杂度$O(n^2 m)$。

考虑区间dp，$f_{i,j}$表示第i个点到第j个点的弧内部全部符合要求的方案数，$g_{i,j}$表示第i个点到第j个点的弧内部全部符合要求且i为最前一个点，j为最后一个点的方案数，$h_{i,j,0}$表示第i个点到第j个点的弧内部加上(i,j)就符合要求的除一个圈未封口以外其他圈已封口且这个未封口的圈内至少有一个企鹅的方案数，$h_{i,j,1}$表示第i个点到第j个点的弧内部加上(i,j)就符合要求的除一个圈未封口以外其他圈已封口且这个未封口的圈内没有企鹅的方案数。

转移时先用前面的$h_{i,j,1}$和f计算当前的$h_{i,j,1}$，再用前面的$h_{i,j,0},h_{i,j,1}$和f计算当前的$h_{i,j,1}$,再用当前和前面的$h_{i,j,0}$计算当前的$g_{i,j}$，最后用当前和前面的$g_{i,j}$计算当前的$f_{i,j}$。

具体细节参见代码