果然 YL 国的 DP 都是码农 DP……
首先按照 x 坐标排序忽略掉一些影响,O(n2) 预处理每个点向四个方向作射线是否会碰到其他点。
DP 时,既然点的影响已经解决了,那么问题在于射线的影响。
可以在状态记录以下四个值: 1. 最右边的向左的射线。 2. 最左边的向右的射线。 3. 最左边的向下的射线。 4. 最右边的向下的射线。
这样,
向上,判断是否与 1,2 相交并转移;
向左,判断是否与 3 相交,更新 1 并转移;
向右,判断是否与 4 相交,更新 2 并转移;
向下,更新 3,4 并转移。
然后第一维要滚动。
代码:
1 |
|