[SDOI2011]打地鼠
题目描述
打地鼠是这样的一个游戏:地面上有一些地鼠洞,地鼠们会不时从洞里探出头来很短时间后又缩回洞中。玩家的目标是在地鼠伸出头时,用锤子砸其头部,砸到的地鼠越多分数也就越高。
游戏中的锤子每次只能打一只地鼠,如果多只地鼠同时探出头,玩家只能通过多次挥舞锤子的方式打掉所有的地鼠。你认为这锤子太没用了,所以你改装了锤子,增加了锤子与地面的接触面积,使其每次可以击打一片区域。如果我们把地面看做m*n的方阵,其每个元素都代表一个地鼠洞,那么锤子可以覆盖R*C区域内的所有地鼠洞。但是改装后的锤子有一个缺点:每次挥舞锤子时,对于这 的区域中的所有地洞,锤子会打掉恰好一只地鼠。也就是说锤子覆盖的区域中,每个地洞必须至少有1只地鼠,且如果某个地洞中地鼠的个数大于1,那么这个地洞只会有1只地鼠被打掉,因此每次挥舞锤子时,恰好有R*C只地鼠被打掉。由于锤子的内部结构过于精密,因此在游戏过程中你不能旋转锤子(即不能互换R和C)。
你可以任意更改锤子的规格(即你可以任意规定R和C的大小),但是改装锤子的工作只能在打地鼠前进行(即你不可以打掉一部分地鼠后,再改变锤子的规格)。你的任务是求出要想打掉所有的地鼠,至少需要挥舞锤子的次数。
Hint:由于你可以把锤子的大小设置为1*1,因此本题总是有解的。
输入输出格式
输入格式:
第一行包含两个正整数m和n;
下面m行每行n个正整数描述地图,每个数字表示相应位置的地洞中地鼠的数量。
输出格式:
输出一个整数,表示最少的挥舞次数。
输入输出样例
3 3
1 2 1
2 4 2
1 2 1
4
说明
【样例说明】
使用2*2的锤子,分别在左上、左下、右上、右下挥舞一次。
【数据规模和约定】
对于30%的数据,m,n<=5 ;
对于60%的数据,m,n<=30 ;
对于100%的数据,1<=m,n<=100 ,其他数据不小于0,不大于10^5 。
直接搜索,加一下剪枝优化即可。
代码实现:
#include<cstdio>
int m,n,a,tot,ans=;
int smap[][],map[][];
void find(int x,int y){
for(int i=;i<=m;i++)
for(int j=;j<=n;j++)
map[i][j]=smap[i][j];
for(int i=;i<=m;i++)
for(int j=;j<=n;j++)
if(map[i][j]){
a=map[i][j];
for(int ii=i;ii<=i+x-;ii++)
for(int jj=j;jj<=j+y-;jj++){
if(map[ii][jj]<a) return;
map[ii][jj]-=a;
}
}
ans=tot/(x*y);
}
int main(){
scanf("%d%d",&m,&n);
for(int i=;i<=m;i++)
for(int j=;j<=n;j++){
scanf("%d",&smap[i][j]);
tot+=smap[i][j];
}
for(int r=m;r>;r--)
for(int c=n;c>;c--)
if(tot%(r*c)==&&tot/(r*c)<ans) find(r,c);
printf("%d\n",ans);
return ;
}
#include<cstdio>
int m,n,a,tot,ans=;
int smap[][],map[][];
int l,ri,ys,ret;
char ch[];
int read(){
ret=,l=ys=;
while(ch[]=getchar())
if(ch[]>=''&&ch[]<='') break;
while(ch[++l]=getchar())
if(ch[l]>''||ch[l]<''){l--;break;}
for(ri=l;ri>;ri--,ys*=) ret+=(ch[ri]-'')*ys;
return ret;
}
void find(int x,int y){
for(int i=;i<=m;i++)
for(int j=;j<=n;j++)
map[i][j]=smap[i][j];
for(int i=;i<=m;i++)
for(int j=;j<=n;j++)
if(map[i][j]){
a=map[i][j];
for(int ii=i;ii<=i+x-;ii++)
for(int jj=j;jj<=j+y-;jj++){
if(map[ii][jj]<a) return;
map[ii][jj]-=a;
}
}
ans=tot/(x*y);
}
int main(){
m=read();n=read();
for(int i=;i<=m;i++)
for(int j=;j<=n;j++){
smap[i][j]=read();
tot+=smap[i][j];
}
for(int r=m;r>;r--)
for(int c=n;c>;c--)
if(tot%(r*c)==&&tot/(r*c)<ans) find(r,c);
printf("%d\n",ans);
return ;
}
为了某些不可告人的目的打的优化版本
ans初值不要赋成100000!!!
题目来源:洛谷
最新文章
- Node Pm2 配置
- __get,__set
- BZOJ-1822 Frozen Nova 冷冻波 计(jie)算(xi)几何+二分+最大流判定+经典建图
- TYVJ P1029 牛棚回声 Label:坑
- [ERROR][org.springframework.web.context.ContextLoader][main] Context initialization failed org.sprin
- UINavigationController 子控制器管理原理
- JNI-使用RegisterNatives注册本地方法
- C# dynamic类型
- Atitit.升级软件的稳定性---基于数据库实现持久化 循环队列 循环队列
- easyui框架--基础篇(一)-->;数据表格datagrid(php与mysql交互)
- java遍历hashMap、hashSet、Hashtable
- appium-doctor问题
- udp_server函数
- 如何利用 LTE/4G 伪基站+GSM 中间人攻击攻破所有短信验证
- Go学习笔记:Win7+LiteIDE+Go+Beego 环境搭建
- LeetCode: Palindrome 回文相关题目
- CR与LF
- [原创]JAVA技巧:去除ArrayList<;Object>;里面的重复记录
- input输入框限制输入英文,数字,汉字
- 接口测试框架开发(二):extentreports报告中文乱码问题
热门文章
- sublime text2 配置php本地环境时遇到的错误。
- 例题 3-5 谜题 uva227 Puzzle
- video 能播放声音不能播放视频,黑屏
- [JOI2014] 小笼包
- MySQL故障处理一例_Another MySQL daemon already running with the same unix socket
- C#手机充值系统开发(基于聚合数据)
- mac当你有多个版本的命令存在是怎么使用最新版本
- javascript入门经典(第五版)-清华出版社之“经典”错误
- HTML 5 <;aside>; 标签
- Springboot + SLF4j + Log4j2 打印异常日志时,耗时要5-6秒