您當(dāng)前位置：首頁(yè) > php開源 > php教程 > 【BZOJ3885】【Usaco2015 Jan】Cow Rectangles 某奇怪的最大子矩形

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

來源：程序員人生發(fā)布時(shí)間：2015-03-30 08:18:12 閱讀次數(shù)：2569次

題意：

坐標(biāo)系上給出n個(gè)點(diǎn)，分”H”和”G”，1個(gè)整點(diǎn)坐標(biāo)上最多1個(gè)點(diǎn)。
現(xiàn)在求1個(gè)不包括”G”的包括盡可能多”H”的子矩形，然后在保證”H”最多的情況下還要問最小面積。
輸出”H”的最大數(shù)量，和保證”H”最多時(shí)的最小矩形面積。

題解：

我們發(fā)現(xiàn)由于坐標(biāo)有限制[0,1000] (注意有”0”!!!)，所以它是1個(gè)矩形。

第1問：

首先我們可以參照極大子矩形的做法算出所有的極大子矩形，然后保護(hù)1個(gè) $f_{i,j}$ 表示 $[1,i][1,j]$ 這個(gè)矩形內(nèi)有多少”H”點(diǎn)，對(duì)1個(gè)矩形O(1)時(shí)間就能夠算出”H”個(gè)數(shù)。

第2問：

以后我們可以把每一個(gè)極大子矩形過剩的邊角砍掉來算面積。
我們可以進(jìn)行2分，看4個(gè)方向都能砍多少，check判的是矩形內(nèi)”H”的個(gè)數(shù)是不是為0。

固然，左右其實(shí)可以均攤O(1)算出來，誒我現(xiàn)在才發(fā)現(xiàn)都已加了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; // 最高距離、最近白點(diǎn)
    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;
}