2012-0035

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

by FJYsmall

首先枚举点的组合和覆盖它的最小的矩形,取枚举点的max_x,max_y,min_x,min_y, 所以min_s = (max_y - min_y + 1) * (max_x - min_x + 1)（这里会爆int）。
如果当前点数能用1个不超过面积s的矩形覆盖,那么减少若干个点也必然能被覆盖。
然后状态压缩DP或者是dfs。
稍微剪枝即可AC。

by FJYsmall

首先枚举点的组合和覆盖它的最小的矩形,取枚举点的max_x,max_y,min_x,min_y, 所以min_s = (max_y - min_y + 1) * (max_x - min_x + 1)（这里会爆int）。

如果当前点数能用1个不超过面积s的矩形覆盖,那么减少若干个点也必然能被覆盖。

然后状态压缩DP或者是dfs。

稍微剪枝即可AC。