题解 P1034 【矩形覆盖】

· · 题解

数据这么小，不写暴搜对不起这么良心的数据啊

本题解介绍如何思路清晰地快速写出暴力。

题目分析:

拿到题面读懂题意后，如此之小的数据范围就告诉我们，这道题不是状压就是暴搜，你说状压吧又没看出来有什么好转移的东西，那就是暴搜跑不脱了。

那么现在有两个方向来搜，一个是枚举每个矩形包含了哪些点，一个是枚举每个点属于哪个矩形。因为我们暴搜的结构需要资瓷回溯，无疑每次只加一个点的后一种结构对于回溯的操作更为友善。

那么dfs的结构呼之欲出：

void dfs(当前考虑的点, 当前总面积) {
    if(当前面积 >= 已有最优解) return;
    if(搜索深度 == n) {
        if(矩形互不相交（满足题面要求）)
            更新最优解;
        return; 
    }
    for(枚举每个矩形) {
        tmp = 当前选定矩形;
        当前点加入选定矩形;
        dfs(下一个点, 新的总面积);
        当前选定矩形 = tmp; #回溯！#
    } 
}

有人可能会问了，为什么要最后才来检查解的合法性呢？

其实对于这么小的数据，效率都差不多：

最后再检查 # 32ms ---/\ VS \/--- 随时检查 # 31ms

考虑到对于矩形这个对象需要资瓷的操作比较多，我们将其封装于一个struct里：

struct mat {
    int lx, ly, rx, ry;//左上角坐标，右下角坐标
    bool cnt;//是否使用过（覆盖着 点）
    void add(int x, int y) {//添加点
        if(!cnt) {//还没用过
            lx = rx = x;
            ly = ry = y;
            cnt = 1;
        } else {//更新覆盖范围
            if(x < lx) lx = x;
            else if(x > rx) rx = x;
            if(y > ly) ly = y;
            else if(y < ry) ry = y;
        }
    }
    bool inmat(int x, int y) const {//判断点是否在矩形里
        return lx <= x && x <= rx && ry <= y && y <= ly;
    }
    int operator() () {//求面积
        if(!cnt) return 0;
        return (rx - lx) * (ly - ry);
    }
    bool operator* (const mat &o) {//判断两个矩形是否相交
        if(!cnt || !o.cnt) return 0;
        return o.inmat(lx, ly) || o.inmat(lx, ry) ||
            o.inmat(rx, ly) || o.inmat(rx, ry);
    }
} km[5];//矩形

有了这么强大的基本操作资瓷，check函数还难写？

bool check() {
    for(int i = 1;i <= k;i++)
        for(int j = i + 1;j <= k;j++)
            if(km[i] * km[j]) return 0;
    return 1;
}

综上所述，您还觉得暴力无从下手？

代码实现:

#include <bits/stdc++.h>
#define N 55
using namespace std;

int n, k, x[N], y[N], ans = INT_MAX >> 2;
struct mat {
    int lx, ly, rx, ry;
    bool cnt;
    void add(int x, int y) {
        if(!cnt) {
            lx = rx = x;
            ly = ry = y;
            cnt = 1;
        } else {
            if(x < lx) lx = x;
            else if(x > rx) rx = x;
            if(y > ly) ly = y;
            else if(y < ry) ry = y;
        }
    }
    bool inmat(int x, int y) const {
        return lx <= x && x <= rx && ry <= y && y <= ly;
    }
    int operator() () {
        if(!cnt) return 0;
        return (rx - lx) * (ly - ry);
    }
    bool operator* (const mat &o) {
        if(!cnt || !o.cnt) return 0;
        return o.inmat(lx, ly) || o.inmat(lx, ry) ||
            o.inmat(rx, ly) || o.inmat(rx, ry);
    }
} km[5];

bool check() {
    for(int i = 1;i <= k;i++)
        for(int j = i + 1;j <= k;j++)
            if(km[i] * km[j]) return 0;
    return 1;
}

void dfs(int i, int area) {
    if(area >= ans) return;
    if(i == n) {
        if(check())
            if(ans > area) ans = area;
        return;
    }
    mat tmp;
    for(int j = 1;j <= k;j++) {
        tmp = km[j];
        km[j].add(x[i], y[i]);
        dfs(i + 1, area - tmp() + km[j]());
        km[j] = tmp;//关键的回溯
    }
}

int main() {
    scanf("%d%d", &n, &k);
    for(int i = 0;i < n;i++)
        scanf("%d%d", x + i, y + i);
    dfs(0, 0);
    printf("%d", ans);
    return 0;
}

后记：

练暴搜的好题，唯一的难点在于回溯，理清楚搜索逻辑 其实并不复杂。