自动搬运

查看原文

来自洛谷，原作者为

	Yukikaze_ **

搬运于2025-08-24 22:15:38，当前版本为作者最后更新于2020-04-10 21:30:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

首先，在一个矩形中选出两个互不相交的小矩形，一定可以用一条水平直线或一条竖直直线将它们分开，这里与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;
}