P2484 [SDOI2011]打地鼠 题解
推荐本蒟蒻的博客
附下AC代码，代码的解释都写在注释里了
#include<bits/stdc++.h> //懒人专用头文件
using namespace std;
int n,m,cnt;
int a[111][111],b[111][111]; //为了防止损坏a数组，判断的操作应在b数组内执行
bool f(int r,int c) //判断长为r，宽为c的锤子是否能够刚好砸完地鼠
{
if(cnt%(r*c))return false; //可行性剪枝：如果地鼠的数量不能被一次砸的地鼠数量整除，那么最后一定不能刚好砸完
else
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
b[i][j]=a[i][j];//复制a数组至b数组
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)//枚举所有的点，一个一个砸下去
{
if(b[i][j]) //如果b[i][j]不为空，那么就将范围内的地鼠数量全都减去它,实现以i，j为左上角砸b[i][j]次锤子
{
int x=b[i][j];
for(int k=1;k<=r;k++)
{
for(int l=1;l<=c;l++)//枚举锤子的范围，将范围内的地鼠都减去b[i][j]
{
if(i+k-1>n || j+l-1>m)return false; //如果锤子的范围超出了n*m，那么返回假
b[i+k-1][j+l-1]-=x; //减去b[i][j]
if(b[i+k-1][j+l-1]<0)return false; //如果锤子将一个位置的地鼠数量砸成了负数，那么也返回假
}
}
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(b[i][j])
{
return false; //在所有位置的地鼠都砸了一遍过后，如果还有位置有地鼠留下，那么同样返回假
}
}
}
return true; //最后，返回真
}
}
int main()
{
cin>>n>>m; //输入n与m
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j]; //输入每个位置的地鼠数量
cnt+=a[i][j]; //统计地鼠一共的数量
}
}
int ans=INT_MAX; //将ans初始化为一个很大的数
for(int i=1;i<=n;i++) //枚举锤子的长
{
for(int j=1;j<=m;j++) //枚举锤子的宽
{
if(f(i,j)) //判断长为i，宽为j的锤子是否能够刚好砸完地鼠
{
ans=min(ans,(cnt)/(i*j)); //需要砸的次数等于地鼠一共的数量除以一次砸的地鼠数量，最后取最小值
}
}
}
cout<<ans; //最后输出答案
return 0;
}