您当前位置：首页 > php开源 > php教程 > 【BZOJ3885】【Usaco2015 Jan】Cow Rectangles 某奇怪的最大子矩形

【BZOJ3885】【Usaco2015 Jan】Cow Rectangles 某奇怪的最大子矩形

来源：程序员人生发布时间：2015-03-30 08:18:12 阅读次数：2393次

题意：

坐标系上给出n个点，分”H”和”G”，1个整点坐标上最多1个点。
现在求1个不包括”G”的包括尽可能多”H”的子矩形，然后在保证”H”最多的情况下还要问最小面积。
输出”H”的最大数量，和保证”H”最多时的最小矩形面积。

题解：

我们发现由于坐标有限制[0,1000] (注意有”0”!!!)，所以它是1个矩形。

第1问：

首先我们可以参照极大子矩形的做法算出所有的极大子矩形，然后保护1个 $f_{i,j}$ 表示 $[1,i][1,j]$ 这个矩形内有多少”H”点，对1个矩形O(1)时间就能够算出”H”个数。

第2问：

以后我们可以把每一个极大子矩形过剩的边角砍掉来算面积。
我们可以进行2分，看4个方向都能砍多少，check判的是矩形内”H”的个数是不是为0。

固然，左右其实可以均摊O(1)算出来，诶我现在才发现都已加了logn了，左右消减还写甚么O(1)啊，噗Qwq。
那就不说了，想知道的自己去看代码吧。

还有就是下面不需要削。
不写了不写了，不懂的留言吧。

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1010
#define inf 0x3f3f3f3f
using namespace std;
int map[N][N],f[N][N];
struct Data
{
    int H,h; // 最高距离、最近白点
    int l,r; // 左右有效距离
}s[N];
int ansa,ansb=inf;
int q[N];
inline int getans(int a,int b,int c,int d){return f[d][b]-f[d][a]-f[c][b]+f[c][a];}
inline int getarea(int a,int b,int c,int d)
{
    int l=c,r=d,mid,ans;
    while(l<=r)
    {
        if(r-l<=3)
        {
            ans=l;
            for(int i=r;i>=l;i--)
                if(getans(a,b,c,i)==0)
                    {ans=i;break;}
            break;  
        }
        mid=l+r>>1;
        if(getans(a,b,c,mid)==0)l=mid;
        else r=mid-1;
    }
    return (b-a-1)*(d-ans-1);
}
int main()
{
    int i,j,k;
    int a,b,c;
    scanf("%d",&c);
    char ss[5];
    while(c--)
    {
        scanf("%d%d%s",&a,&b,ss),a++,b++;
        if(ss[0]=='H')map[a][b]=1; // 可
        else map[a][b]=2; // 否
    }
    for(i=1;i<=1001;i++)
    {
        int temp=0;
        for(j=1;j<=1001;j++)
        {
            if(map[i][j]==1)temp++;
            f[i][j]=f[i-1][j]+temp;
        }
    }
    for(i=1;i<=1001;i++)s[i].h=inf;
    int l,r;
    for(i=1;i<=1001;i++)
    {
        for(j=1;j<=1001;j++)
        {
            if(map[i][j]==2)s[j].H=0,s[j].h=inf;
            else {
                s[j].H++;
                if(map[i][j]==1)s[j].h=1;
                else s[j].h++;
            }
            s[j].l=s[j].r=j;
        }
        l=1,r=0;
        for(j=1;j<=1001;j++)
        {
            while(l<=r&&s[q[r]].H>=s[j].H)s[j].l=s[q[r--]].l;
            while(s[j].l<j&&s[s[j].l].h>s[j].H)s[j].l++;
            q[++r]=j;
        }
        l=1,r=0;
        for(j=1001;j;j--)
        {
            while(l<=r&&s[q[r]].H>=s[j].H)s[j].r=s[q[r--]].r;
            while(s[j].r>j&&s[s[j].r].h>s[j].H)s[j].r--;
            q[++r]=j;
        }
        for(j=1;j<=1001;j++)
        {
            int ret=getans(s[j].l-1,s[j].r,i-s[j].H,i);
            if(ret>=ansa)
            {
                int temp=getarea(s[j].l-1,s[j].r,i-s[j].H,i);
                if(ret==ansa)ansb=min(ansb,temp);
                else ansa=ret,ansb=temp;
            }
        }
    }
    printf("%d
%d
",ansa,ansb);
    return 0;
}