P5975 题解

Oct_ · 2024-02-19 17:08:14 · 题解

首先，特别感谢 @XuYueming 和 @sbno333 以及这篇帖子，Hack 数据已修复，现提供一种更优做法。

题目传送门

题目大意

给出平面上 n \le 100 个点，求最少用多少个面积 \le 200000 的矩形才能全覆盖。

解题思路

如果两个矩形相交且不是包含关系，那么完全可以让它们不相交。

将坐标离散化后，设 f_{i,j,k} 表示区间 [i,j] 纵坐标不小于 k 的部分的最优解。

对于 f_{i,j,k}，要么枚举分割线，分成两部分分别 DP，要么放入一个尽量大的矩形，转化为子区间的问题。

时间复杂度 O(n^4)。

AC code：

#include<bits/stdc++.h>
using namespace std;
int n,m,A,i,j,k,t,x,y,l,r,b[110],c[110],f[110][110][110];
struct data
{
    int x,y;
}a[110];
bool cmp(data a,data b)
{
    return a.x==b.x?a.y>b.y:a.x<b.x;
}
inline void dfs(int&a,int b)
{
    if(a>b)a=b;
}
int main()
{
    scanf("%d%d",&n,&A);
    for(i=1;i<=n;i++)
        scanf("%d%d",&a[i].x,&a[i].y);
    sort(a+1,a+n+1,cmp);
    for(i=1;i<=n;i++)
        if(i==1||a[i].x!=a[i-1].x)
            a[++m]=a[i];
    for(i=1;i<=m;i++)
        b[i]=a[i].y;
    sort(b+1,b+m+1);
    for(i=1;i<=m;i++)
        for(j=1;j<=m;j++)
            if(a[i].y==b[j])
            {
                c[i]=j;
                break;
            }
    for(i=m;i;i--)
        for(j=i;j<=m;j++)
            for(k=m;k;k--)
            {
                for(f[i][j][k]=110,t=i;t<j;t++)
                    dfs(f[i][j][k],f[i][t][k]+f[t+1][j][k]);
                for(l=i;l<=j;l++)
                    if(c[l]>=k) break;
                for(r=j;r>=i;r--)
                    if(c[r]>=k) break;
                if(l>r)
                {
                    f[i][j][k]=0;
                    continue;
                }
                if(l==r)
                {
                    f[i][j][k]=1;
                    continue;
                }
                x=a[r].x-a[l].x,y=A/x;
                for(l=i;l<=j;l++)
                    if(a[l].y>y) break;
                for(r=j;r>=i;r--)
                    if(a[r].y>y) break;
                for(x=110,t=l;t<=r;t++)
                    if(a[t].y>y&&c[t]<x) x=c[t];
                dfs(f[i][j][k],f[l][r][x]+1);
            }
    printf("%d",f[1][m][1]);
    return 0;
}

附上我的 AC 记录！

如有不对的地方还请大家多多指正，感谢大家！！！