如果我们确定了(r)和(c),事实上也确定了打地鼠的方案。
因为所有(r imes c)的矩形中,只有1个能覆盖当前还有地鼠的位置组成的图形的角落上的那个洞,所以我们只能在那个角落上砸。
比如,我们目前剩下的地鼠分布为
0 0 0 0
0 0 1 2
0 2 1 2
2 2 3 1
那么我们只能以第二行的第三个位置(那个加粗的1)为左上角砸1次。
做法1
于是我们可以(O(nm))枚举(r),枚举(c),然后(O(nm))从左到右,从上到下枚举点,然后(O(rc))给以当前点为左上角的矩形内的数减去当前点剩下的地鼠数量,寻找(r imes c)的最大值。
然而这样做是(O(n^3m^3))的。
我们可以做一下二维差分,然后省去了最后给矩形内点减去当前点剩下的地鼠数量的步骤。
二维差分:给一个左上端点为((x_1,y_1)),右下端点为((x_2,y_2))的矩形加上(v),需要在差分数组的(s_{x_1,y_1})和(s_{x_2+1,y_2+1})加上(v),给(s_{x_1,y_2+1})给(s_{x_2+1,y_1})减去(v),那么左上端点为((1,1)),右下端点为((x,y))的矩形的和就是点((x,y))上的实际值了。
时间复杂度(O(n^2m^2))。
code:
#include<bits/stdc++.h>
#define Add(u,l,d,r,v) (sum[u][l]+=v,sum[d+1][r+1]+=v,sum[u][r+1]-=v,sum[d+1][l]-=v)
using namespace std;
int n,m,num[110][110],sum[110][110],ans,t,SUM;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)scanf("%d",&num[i][j]),SUM+=num[i][j];
for(int r=1;r<=n;++r){
for(int c=1;c<=m;++c){
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)sum[i][j]=0;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
if(sum[i][j]>num[i][j])goto END;
if(sum[i][j]<num[i][j]){
if(i+r-1>n||j+c-1>m)goto END;
t=num[i][j]-sum[i][j],Add(i,j,i+r-1,j+c-1,t);
}
}
}
ans=max(ans,r*c);
END:
;
}
}
printf("%d",SUM/ans);
return 0;
}
做法2
我们枚举(r),假定(c=1),计算最大的合法的(r);
然后假定(r=1),枚举(c),计算最大的合法的(c);
那么(r imes c)锤子一定是可行的。
为什么呢?
证明:
我们每次锤的点是目前地鼠数非0的位置组成的图形中最上一行最左一列的点，我们设这个点还有(x)只地鼠。
首先,以这个点为左上端点,锤一个(1 imes c)的矩形(x)次是合法的;
其次,以这一行前(c)个点每一个为左上端点,各锤一个(r imes 1)的矩形(x)次是合法的。
所以这个(r imes c)矩形也就是合法的了。
时间复杂度(O((n+m)nm))。
code:
#include<bits/stdc++.h>
using namespace std;
int n,m,num[110][110],sum[110][110],r,c,t,SUM;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)scanf("%d",&num[i][j]),SUM+=num[i][j];
for(r=n;r>=1;--r){
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)sum[i][j]=0;
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){
sum[i][j]+=sum[i-1][j];
if(sum[i][j]>num[i][j])goto END1;
if(sum[i][j]<num[i][j]){
if(i+r-1>n)goto END1;
else t=num[i][j]-sum[i][j],sum[i][j]+=t,sum[i+r][j]-=t;
}
}
break;
END1:
;
}
for(c=n;c>=1;--c){
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)sum[i][j]=0;
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){
sum[i][j]+=sum[i][j-1];
if(sum[i][j]>num[i][j])goto END2;
if(sum[i][j]<num[i][j]){
if(j+c-1>m)goto END2;
else t=num[i][j]-sum[i][j],sum[i][j]+=t,sum[i][j+c]-=t;
}
}
break;
END2:
;
}
printf("%d",SUM/(r*c));
return 0;
}