题解 P5975 【[CEOI2009]photo】

· · 题解

数据极水，建议加强数据。

题意：用尽可能较少的一边在 x 轴上的面积小于等于 m 的矩形覆盖全部 n 个点。

首先，可以发现 x 坐标相同的点只需要保留 y 坐标最大的点就够了，因为题面要求矩形一边在 x 轴上，如果对于相同 x，y 更大的点被覆盖，那么这个矩形一定会同时覆盖 y 较小的点，于是这样的点不需要考虑。

于是我们可以先将 x、y 坐标离散化；对于 x 坐标相同的点仅保留最大的 y。

设 f_{i,j,k} 表示将离散化后， x 坐标在 [i,j]，y 坐标在 [1,k] 中的点覆盖的最小代价。

转移有两种：

  1. 左右区间分开覆盖：

    f_{i,j,k}=\min_{a=i}^{j-1}\{f_{i,a,k}+f_{a+1,j,k}\}

  2. 先通过某种方式覆盖 y 值较小的所有点，再将 y 值较大的点直接一次覆盖。

    f_{i,j,k}=\min_{a\in[0,k)\cup(r-l)\times y_{\max}\leq m}\{f_{i,j,a}+1\}

    其中 l、r 表示 x\in[i,j],y\in(a,k] 的点中 x 值所在区间。(r-l)\times y_{\max}\leq m 表示要求一次覆盖的点的所需矩形的面积不超过 m。

边界条件：

  1. f_{i,i,k}=[y_i\leq k]
  2. f_{i,j,0}=0

    理由：没有点时不需要矩形覆盖。

时间复杂度： \mathbf O(n^4)

AC代码

ps：这题好像还有一种dfs转移的做法，跑得飞快。。。