P5975

lucky叶 · 2022-02-09 11:55:50 · 题解

感谢sbno333的hack，已修锅。

您是否做题时常有推不出 dp 而懊恼。

既然推不出来，那就用暴力消灭它。

Solution

我们考虑暴力，矩形的一条边已经在 x 轴上，那么由贪心可得存在最优解满足所有矩形的另外三条边上都有点，但其实只要两个点就可以确定矩形了，考虑 O(n^2) 枚举左右边上的点，每个矩形尽量往上用完面积，处理出这 n^2 个矩形各自覆盖的点，问题转化为在这 n^2 个矩形中选最少的矩形(其实没有这么多，除去重复的后还挺少的)，保证覆盖所有点，但如何确定选哪几个矩形呢？

等等，当每个矩形都确定了，那么可覆盖的点也就确定了，这貌似是 Dancing Links 的重复覆盖问题？

上板子即可（好像因为数据水，贪心也能过）。

code

#include<bits/stdc++.h>
using namespace std;
const int N = 10010;
int n, m;
int l[N], r[N], u[N], d[N], s[N], row[N], col[N], idx;
int ans[N], top;
bool st[110];
void init()
{
    for(int i = 0;i <= m;i ++)
    {
        l[i] = i - 1, r[i] = i + 1;
        col[i] = u[i] = d[i] = i;
        s[i] = 0;
    }
    l[0] = m, r[m] = 0;
    idx = m + 1;
}
int h()
{
    int cnt = 0;
    memset(st, 0, sizeof(st));
    for(int i = r[0]; i;i = r[i])
    {
        if(st[col[i]]) continue;
        cnt ++;
        st[col[i]] = true;
        for(int j = d[i];j != i;j = d[j])
            for(int k = r[j];k != j;k = r[k])
                st[col[k]] = true;
    }
    return cnt;
}
void add(int &hh, int &tt, int x, int y)
{
    row[idx] = x, col[idx] = y, s[y] ++;
    u[idx] = y, d[idx] = d[y], u[d[y]] = idx, d[y] = idx;
    r[hh] = l[tt] = idx, r[idx] = tt, l[idx] = hh;
    tt = idx ++;
}
void remove(int p)
{
    for(int i = d[p];i != p;i = d[i])
    {
        r[l[i]] = r[i];
        l[r[i]] = l[i];
    }
}
void resume(int p)
{
    for(int i = u[p];i != p;i = u[i])
    {
        r[l[i]] = i;
        l[r[i]] = i;
    }
}
bool dfs(int k, int depth)
{
    if(k + h() > depth) return false;
    if(!r[0]) return true;
    int p = r[0];
    for(int i = r[0]; i;i = r[i])
    {
        if(s[p] > s[i])
            p = i;
    }
    for(int i = d[p]; i != p;i = d[i])
    {
        ans[k] = row[i];
        remove(i);
        for(int j = r[i]; j != i;j = r[j]) remove(j);
        if(dfs(k + 1, depth)) return true;
        for(int j = l[i]; j != i;j = l[j]) resume(j);
        resume(i);
    }
    return false;
}
int a, b;
struct Node{
    int x, y;
    bool operator< (Node c)const
    {
        if(x == c.x) return y < c.y;
        return x < c.x;
    }
}p[N];
int main()
{   
    scanf("%d%d", &a, &b);
    m = a;
    init();
    for(int i = 1;i <= a;i ++)
        scanf("%d%d", &p[i].x, &p[i].y);
    sort(p + 1, p + a + 1);
    for(int i = 1;i <= a;i ++)
    {
        for(int j = i + 1;j <= a;j ++)
        {
            if(p[i].x == p[j].x || b / max(p[i].y, p[j].y) + p[i].x < p[j].x) continue;
            int hh = idx, tt = idx;
            n ++;
            for(int k = i;k <= a;k ++)
            {
                if(p[k].x > b / max(p[i].y, p[j].y) + p[i].x) break;
                if(p[k].y <= max(p[i].y, p[j].y)) add(hh, tt, n, k);
            }
        }
        int hh = idx, tt = idx;
        n ++;
        for(int j = 1;j <= a;j ++)
            if(p[i].x == p[j].x) add(hh, tt, n, j);// 可能有极高点，需要单独取矩形, 注意，这个单独的矩形可以是无穷高，所以这条线上的点都可以被覆盖（之前没注意到）
    }
    int depth = 0;
    while(!dfs(0, depth)) depth ++;
    printf("%d\n", depth);
    return 0;
}