题解P1034【矩形覆盖】

Desert_Lycoris · 2020-08-15 17:11:06 · 题解

第一篇题解

本蒟蒻人生中的第一篇题解，如有错误，还请各位见谅。

读题

需要注意两点：

1. 题目中的点是以（y，x）的形式给出的，而不是（x，y）。

思路

大体上的思路是深搜，不过本蒟蒻是按照点来进行的深搜（应该和大多数题解不太一样）。

解题步骤

第一步——预处理

将所有的点按照升序排列存入px数组中。

struct point
{
    int x, y;
}px[510];//px[i]表示横坐标第i大的点

bool compx(point a, point b)
{
    return a.x < b.x;
}//升序排列

sort(px+1, px+n+1, compx);//sort函数排序

用动态规划（dp）求出区间中纵坐标的最大值及最小值

struct dx
{
    int maxx, minn;
}py[510][510];
//py[i][j].maxx表示从px[i]到px[j]所有点中纵坐标最大的点的纵坐标
py[i][j].minn表示从px[i]到px[j]所有点中纵坐标最小的点的纵坐标

for(int i = 1; i <= n; i++)
{
   for(int j = i; j <= n; j++)//j从i开始而不是1开始
   {
     if(i == j){py[i][j].maxx = py[i][j].minn = px[i].y;}
     else
     {
       py[i][j].maxx = max(py[i][j-1].maxx, px[j].y);
       py[i][j].minn = min(py[i][j-1].minn, px[j].y);
     }
   }
}//动态规划求py数组

预处理部分结束之后，就来到了本题的第二个关键点——深搜

第二步——深度优先搜索

这里，我们需要用两个变量（i，p）来表示当前的状态。

其中，i表示当前是第i个矩形；p表示第i个矩形从横坐标第p大的点开始。

另外，我们还需要有ok和pre这两个变量。