换个角度来想 ， 我们已经统计出 \(sum\) ， 现在正在枚举 \(i\times j\) 型号的锤子 。若这种锤子满足要求，就应该满足：\(sum\) 是\(i\times j\) 的整数倍 。在此基础上再判断该型号的锤子能否锤尽全图地鼠，若能，则答案 \(ans=sum/i/j\) .可以节省不少时间 。这里枚举 \(i\) 和 \(j\) ,就可以从\(1\)~\(n\) 进行，这样 \(i\) 和 \(j\) 越枚举越大，\(ans\) 也就越来越小，省去了比较大小的过程 。
除此之外我们还可以进行剪枝 。
若当前的 \(sum/i/j\) 小于已经算出来的 \(ans\)，则当前情况必不可能为最优情况 。
AC代码：
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=105;int a[N][N],b[N][N],n,m,ans,sum;bool check(int x,int y){ memcpy(b,a,sizeof(a)); for(int i=1;i<=n-x+1;i++) {for(int j=1;j<=m-y+1;j++){if(b[i][j]){int z=b[i][j];for(int k=0;k<x;k++){for(int l=0;l<y;l++){b[i+k][j+l]-=z;if(b[i+k][j+l]<0) return 0;}}}} } for(int i=1;i<=n;i++) {for(int j=1;j<=m;j++){if(b[i][j]) return 0;} } return 1;}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) {for(int j=1;j<=m;j++){scanf("%d",&a[i][j]);sum+=a[i][j];} } ans=sum; for(int i=1;i<=n;i++) {for(int j=1;j<=m;j++){if(sum%(i*j)==0&&sum/i/j<ans){if(check(i,j)) ans=sum/i/j;}} } printf("%d\n",ans); return 0;}【susliks 打地鼠 方法记录】
推荐阅读
- 二 Three光线检测-实现摄像机向鼠标点击位置滑动动画
- 四 Selenium4.0+Python3系列 - 常见元素操作（含鼠标键盘事件）
- 超强的纯 CSS 鼠标点击拖拽效果
- 根据不同时辰看生肖属鼠的财运，属鼠的你必看
- 发现家里有老鼠怎么办 家里有老鼠怎么能彻底消灭
- 有什么方法可以快速去除房间的老鼠？
- 家中有老鼠如何驱赶 家里有老鼠怎么办才能快速驱赶
- 猫和老鼠s9赛季皮肤 s9赛季皮肤有哪些
- 兰皮鼠与大脸猫的好词好句佳句分享？
- 海南一男子被竹叶青咬伤 小白鼠血清多少钱一升