Description：

给出 $n$ 个必须覆盖的点的坐标 $(x[i],y[i])$ 和 $m$ 个不能覆盖的点的坐标 $(x'[i],y'[i])$ ，每次可以选一个下边界紧贴 $x$ 轴的矩形，要求把所有必盖点都覆盖并且不覆盖不能覆盖的点，对于 $n$ 的 $2^n$ 个子集输出最少需要的矩形数之和。

$1\leqslant n\leqslant 1000$

Solution：

首先我们求出 $mn[p]=\min y'[i](x[p]<x'[i]<x[p+1]$ ，那么我们可以按照 $mn[p]$ 建出一棵笛卡尔树，那么我们可以把树上一个点看成一个区间 $[l,r]$ ，或者是一个宽为 $[l,r]$ ，高为 $h[l,r]=\min mn[p]\ p\in[l,r)$ ，如果 $l=r$ 那么表示的就是 $(x[l],y[l])$ 这个点，那么显然能覆盖一个点的矩形一定是从 $[i,i]$ 开始往上的一条链，这个可以预处理出来每条链的最高点，然后我们的问题就变成了给树上一些从叶子开始的直上直下的链，选一些点使得每条链中都有点，我们就有了一个线性的贪心算法， $f[i]$ 表示在 $i$ 这个点子树内还没有被覆盖的深度的最大值，如果 $f[i]=dep[i]$ ，那么显然必须在 $i$ 这里放一个，那么对于对所有子集求和的询问，我们可以使用 $DP$ 套 $DP$ ，也就是设 $f[i][j]$ 表示在第 $i$ 个点 $f[i]=j$ 的状态的个数，然后每次加上 $f[i][dep[i]]$ 即可。

Code：

没有代码