题解 P5920 【[IOI2005]gar】

· · 题解

并不需要什么算法的一道题，暴力就可以过。

首先，在一个矩形中选出两个互不相交的小矩形，一定可以用一条水平直线或一条竖直直线将它们分开，这里与APIO2009 采油区域有些类似，不过那题是三个矩形，情况要多一些。

知道了这一点后，我们就可以考虑枚举分界线了，为了能在枚举分界线时更快地统计答案，我们需要把每一列向左、右，每一行向上、下延伸出的符合条件的周长最小的矩形计算出来，这里朴素算法是O(n^4)的（枚举每个组合），所以需要一些小优化，我用了n^2个队列对应每条线段统计答案，复杂度为O(n^3)。

然后，我们枚举分界线，并分别取分界线前后的最小值加起来更新答案就可以了。加上预处理，总复杂度O(n^3)。

接下来是我写代码时的一个小细节（可能并没有什么用）：四个方向预处理的过程很类似，可以考虑将矩形旋转3次然后用一个函数解决来减少码量。

然后是代码

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
const int N=255,inf=1e9;
int h[N][N],sum[N][N],r,c,n,k;
int dt[N][N],zuo[N][N],ans=inf;
int up[N],down[N],rt[N],lf[N];
int read()
{
    int res=0,fl=0;
    char a=getchar();
    while(a<'0'||a>'9') {if(a=='-') fl=1;a=getchar();}
    while(a>='0'&&a<='9') res=res*10+a-'0',a=getchar();
    return fl? -res:res;
}
void work(int lr,int lc,int *lx)
{
    int i,j,li;
    for(i=1;i<=lr;i++)
        for(j=1;j<=lc;j++) zuo[i][j]=zuo[i][j-1]+dt[i][j]; //预处理每行前缀和 
    for(i=1;i<=lc;i++)
        for(j=i;j<=lc;j++) h[i][j]=1,sum[i][j]=0; //还原指针和总和 
    for(i=1;i<=lr;i++)
    {
        lx[i]=inf;
        for(j=1;j<=lc;j++)
            for(li=j;li<=lc;li++)
            {
                sum[j][li]+=zuo[i][li]-zuo[i][j-1];
                while(sum[j][li]>k) sum[j][li]-=zuo[h[j][li]][li]-zuo[h[j][li]][j-1],h[j][li]++; //如果总和大于k就舍弃最后一行
                if(sum[j][li]==k) lx[i]=min(lx[i],(li-j+1+i-h[j][li]+1)<<1); //如果处理完后总和刚好为k就更新答案 
            }
    }
}
void rotate(int lr,int lc)
{
    int res[N][N]={{0}};
    for(int i=1;i<=lc;i++)
        for(int j=1;j<=lr;j++) res[i][j]=dt[lr-j+1][i];
    memcpy(dt,res,sizeof(dt));
}
int main()
{
//  freopen("gar.in","r",stdin);
//  freopen("gar.out","w",stdout);
    int i,j,li,lj;
    r=read(),c=read(),n=read(),k=read();
    for(i=1;i<=n;i++)
    {
        int lr=read(),lc=read();
        dt[lr][lc]++;
    }
    work(r,c,up),rotate(r,c),work(c,r,lf),rotate(c,r),work(r,c,down),rotate(r,c),work(c,r,rt),rotate(c,r); //旋转4次统计答案 
    for(i=2;i<=r;i++) up[i]=min(up[i],up[i-1]),down[i]=min(down[i],down[i-1]); 
    for(i=2;i<=c;i++) lf[i]=min(lf[i],lf[i-1]),rt[i]=min(rt[i],rt[i-1]); //前缀取最小值 
    for(i=1;i<c;i++) ans=min(ans,lf[i]+rt[c-i]);
    for(i=1;i<r;i++) ans=min(ans,up[i]+down[r-i]);
    cout<<ans;
    return 0;
}