一、题目

点此看题

二、解法

首先考虑一维的情况，设平面上的草位置分别是 \(1\leq x_1<x_2...<x_n\leq c\)，那么答案是：

我们枚举上下方向的风，然后对每行独立做，时间复杂度 \(O(R^3)\)

可以把行离散化成若干个左闭右开的区间，每个区间内草的分别是相同的，可以统一计算，时间复杂度 \(O(R^2n)\)

有一个关键的 \(\tt observation\) 是：如果不考虑边界，上下方向吹一次得到的网格图是同构的。那么我们可以枚举上下吹的总次数 \(L\)，然后把原图向下吹 \(L\) 次，然后在 \([1,n+L]\) 这些行中选取连续的 \(R\) 行就得到了目标的矩形。

发现是一个长度为 \(L\) 的滑动窗口问题，需要对 \(x_1-1/c-x_n/\max_{1\leq i<n} x_{i+1}-x_i-1\) 这三部分分别维护单调队列，然后枚举区间左端点计算答案，那么时间复杂度 \(O(Rn)\)

现在要把 \(R\) 拿出时间复杂度中，一个想法是减少 \(L\) 的取值数量，发现只有这些 \(L\) 是有用的：

• 能覆盖完整个网格，最小的 \(L\)（按照一维的方式计算得出）
• 对于任意 \(i,j\)，\(i\) 吹到了下边界，\(j\) 吹到的上边界，需要的次数 \(L\)
• 对于任意 \(i,j\)，\(i\) 和 \(j\) 在中间碰头所需要的次数 \(L\)

所以 \(L\) 的取值个数是 \(O(n^2)\)，我们预处理出行的区间 \([i,j]\) 合并的结果 \(f[i][j]\)（还是要三部分），枚举 \(L\) 之后先离散化，然后用 \(f\) 得到每个行合并的结果，再跑单调队列即可，时间复杂度 \(O(n^3)\)

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
const int M = 605;
#define int long long
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int r,c,n,m,ans,b[M];
struct node{int x,y,z;}a[M],f[M][M],g[M];
struct zxy
{
	int h,t,s[M],v[M];
	zxy() {t=0;h=1;}
	void push(int x,int y)
	{
		for(;h<=t && v[t]<=y;t--);
		s[++t]=x;v[t]=y;
	}
	void pop(int x)
	{
		for(;h<=t && s[h]<=x;h++);
	}
	int top() {return v[h];}
};
int calc(int L)
{
	m=0;
	for(int i=1,j=1;i<=n || j<=n;)
	{
		if(j>n || (i<=n && a[i].x<=a[j].x+L))
			b[++m]=a[i++].x;
		else b[++m]=a[j++].x+L+1;
	}
	m=unique(b+1,b+1+m)-b-1;
	for(int i=1,j=1,k=1;i<=m;g[i++]=f[j][k])
	{
		for(;j<n && a[j].x+L<b[i];j++);
		for(;k<n && a[k+1].x<=b[i];k++);
	}
	int mi=c+c;zxy X,Y,Z;
	for(int i=1,j=1;i<=m;i++)
	{
		for(;j<=m && b[i]+r>b[j];j++)
			X.push(j,g[j].x),Y.push(j,g[j].y),Z.push(j,g[j].z);
		if(j>m) break;
		mi=min(mi,max(X.top()+Z.top(),Y.top()));
		X.pop(i);Y.pop(i);Z.pop(i);
	}
	return mi;
}
signed main()
{
	r=read();c=read();n=read();ans=r+c;
	for(int i=1;i<=n;i++)
		a[i].x=read(),a[i].y=read();
	sort(a+1,a+1+n,[&](node u,node v)
	{return u.x<v.x;});
	for(int i=1;i<=n;i++)
	{
		set<int> s;
		for(int j=i;j<=n;j++)
		{
			s.insert(a[j].y);m=0;
			for(int x:s) b[++m]=x;
			f[i][j]={b[1]-1,0,c-b[m]};
			for(int k=1;k<m;k++)
				f[i][j].y=max(f[i][j].y,b[k+1]-b[k]-1);
		}
	}
	int L=a[1].x-1+r-a[n].x;
	for(int i=1;i<n;i++) L=max(L,a[i+1].x-a[i].x-1);
	ans=L+calc(L);
	for(int i=1,t=0;i<=n;i++) for(int j=1;j<=n;j++)
	{
		if((t=a[i].x-a[j].x-1)>L)
			ans=min(ans,t+calc(t));
		if((t=r-a[i].x+a[j].x-1)>L)
			ans=min(ans,t+calc(t));
	}
	printf("%lld\n",ans);
}