BZOJ 1207
1207: [HNOI2004]打鼹鼠
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 3089 Solved: 1499
[Submit][Status][Discuss]
Description
鼹鼠是一种很喜欢挖洞的动物,但每过一定的时间,它还是喜欢把头探出到地面上来透透气的。根据这个特点阿Q编写了一个打鼹鼠的游戏:在一个n*n的网格中,在某些时刻鼹鼠会在某一个网格探出头来透透气。你可以控制一个机器人来打鼹鼠,如果i时刻鼹鼠在某个网格中出现,而机器人也处于同一网格的话,那么这个鼹鼠就会被机器人打死。而机器人每一时刻只能够移动一格或停留在原地不动。机器人的移动是指从当前所处的网格移向相邻的网格,即从坐标为(i,j)的网格移向(i-1, j),(i+1, j),(i,j-1),(i,j+1)四个网格,机器人不能走出整个n*n的网格。游戏开始时,你可以自由选定机器人的初始位置。现在你知道在一段时间内,鼹鼠出现的时间和地点,希望你编写一个程序使机器人在这一段时间内打死尽可能多的鼹鼠。
Input
第一行为n(n<=1000), m(m<=10000),其中m表示在这一段时间内出现的鼹鼠的个数,接下来的m行每行有三个数据time,x,y表示有一只鼹鼠在游戏开始后time个时刻,在第x行第y个网格里出现了一只鼹鼠。Time按递增的顺序给出。注意同一时刻可能出现多只鼹鼠,但同一时刻同一地点只可能出现一只鼹鼠。
Output
仅包含一个正整数,表示被打死鼹鼠的最大数目
Sample Input
1 1 1
2 2 2
Sample Output
HINT
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std; int f[],t[],x[],y[]; int abs(int a)
{
if(a<)return -a;
else return a;
} bool check(int i,int j)
{
if((abs(x[j]-x[i])+abs(y[j]-y[i]))<=abs(t[j]-t[i]))
return true;
else return false;
} int main()
{
int n,m,ans=;
fill(f+,f++,);
scanf("%d%d",&n,&m);
for(int i=;i<=m;++i)
{
scanf("%d%d%d",&t[i],&x[i],&y[i]);
for(int j=;j<i;++j)
if(check(i,j))
f[i]=max(f[i],f[j]+);
ans=max(f[i],ans);
}
printf("%d",ans);
}
就是一维数组记录在打第i只地鼠时所能打死的最多地鼠的数量
然后用i之前的至来更新他
好像二重循环比较慢的样子,需要m^2 ,但是好像是能优化掉一个m的,到log级别
只是看黄学长的优化方法,好像有点懵
做这个题有一点需要格外注意, f 数组一开始要初始化为 1 ,因为一开始的那只地鼠是肯定能打掉的……
第二种做法
是黄学长的优化,看起来好像与m^2做法没什么不同,但是好像结果很出人意料
#include<iostream>
#include<cstdio>
#define maxn 10005
using namespace std; int m,n;
int fx[maxn],x[maxn],y[maxn],t[maxn],f[maxn]; int abs(int a)
{
if(a<)return -a;
else return a;
} bool judge(int i,int j)
{
if((abs(x[j]-x[i])+abs(y[j]-y[i]))<=abs(t[j]-t[i]))
return true;
else return false;
} int main()
{
scanf("%d%d",&n,&m);
int ans=;
fx[]=;
for(int i=;i<=m;++i)
{
f[i]=true;
scanf("%d%d%d",&t[i],&x[i],&y[i]);
for(int j=i-;j>=;--j)
{
if(fx[j]<f[i])break;
if(f[j]<f[i])continue;
if(judge(i,j))f[i]=f[j]+;
}
fx[i]=max(fx[i-],f[i]);
ans=max(ans,f[i]);
}
printf("%d",ans);
return ;
}
仿佛变了魔术……从4754MS优化到60MS,我只是稍微写了个优化而已……
就是加了个数组记录最优解而已,然后在不可能的情形下退出循环而已……
竟然快了这么多……
这个题启示我们优化一定要好好学……
这可能也是我这几天见过的最简单的BZOJ的题了吧,竟然能水过去……
最新文章
- One Page Scroll – 实现苹果风格的单页滚动效果
- Vijos P1769 网络的关键边
- js中关于prototype学习(2015年1月5号晚)
- VS2010调试入门指南
- [转]一步步教你如何在 Visual Studio 2013 上使用 Github
- Android AsyncTask 初探
- python3--(变量)
- oracle如何设置show parameter显示隐含参数
- HDU - 1205 I NEED A OFFER!
- 享元模式(Flyweight)
- child_process 子进程
- 如何正确使用Java泛型
- main函数的的两个参数
- Windows Server 2016-Win Ser 2016新增功能
- servlet ServletContext
- 八皇后(DFS)
- C#.NET常见问题(FAQ)-如何让控件或者窗体本身全屏
- C# 校验Email(电子邮件)地址是否合法
- 国内首款 FPGA 云服务器,性能是通用 CPU 服务器 30 倍以上
- 让网页的title动起来