luoguP2285 [HNOI2004]打鼹鼠 x
2024-09-05 08:29:43
P2285 [HNOI2004]打鼹鼠
题目描述
鼹鼠是一种很喜欢挖洞的动物,但每过一定的时间,它还是喜欢把头探出到地面上来透透气的。根据这个特点阿牛编写了一个打鼹鼠的游戏:在一个n*n的网格中,在某些时刻鼹鼠会在某一个网格探出头来透透气。你可以控制一个机器人来打鼹鼠,如果i时刻鼹鼠在某个网格中出现,而机器人也处于同一网格的话,那么这个鼹鼠就会被机器人打死。而机器人每一时刻只能够移动一格或停留在原地不动。机器人的移动是指从当前所处的网格移向相邻的网格,即从坐标为(i,j)的网格移向(i-1, j),(i+1, j),(i,j-1),(i,j+1)四个网格,机器人不能走出整个n*n的网格。游戏开始时,你可以自由选定机器人的初始位置。
现在知道在一段时间内,鼹鼠出现的时间和地点,请编写一个程序使机器人在这一段时间内打死尽可能多的鼹鼠。
输入输出格式
输入格式:
从文件input.txt中读入数据,文件第一行为n(n<=1000), m(m<=10000),其中m表示在这一段时间内出现的鼹鼠的个数,接下来的m行中每行有三个数据time,x,y表示有一只鼹鼠在游戏开始后time个时刻,在第x行第y个网格里出现了一只鼹鼠。Time按递增的顺序给出。注意同一时刻可能出现多只鼹鼠,但同一时刻同一地点只可能出现一只鼹鼠。
输出格式:
输出文件output.txt中仅包含一个正整数,表示被打死鼹鼠的最大数目。
输入输出样例
输入样例#1:
2 2
1 1 1
2 2 2
输出样例#1:
1
思路:
dp
dp[i]表示到第i只鼹鼠最多能够打多少只.
转移方程为dp[j]=max{dp[i]+1},条件:abs(x[j]-x[i])+abs(y[j]-y[i])<=time[j]-time[i] (j>i)
坑点:
n没用
上代码:
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std; const int M = ;
int n,m,ans;
int t[M],x[M],y[M];
int dp[M]; int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&t[i],&x[i],&y[i]);
dp[i]=;
}
for(int i=;i<m;i++)///或者1~m也可以
{
for(int j=i+;j<=m;j++)
if(abs(x[j]-x[i])+abs(y[j]-y[i])<=t[j]-t[i])
dp[j]=max(dp[j],dp[i]+);
ans=max(ans,dp[i+]);
}
printf("%d",ans);
return ;
}
或者还可以
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std; const int M = ;
int n,m,ans;
int t[M],x[M],y[M];
int dp[M]; int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&t[i],&x[i],&y[i]);
dp[i]=;
}
for(int i=;i<=m;i++)
{
for(int j=i+;j<=m;j++)
if(abs(x[j]-x[i])+abs(y[j]-y[i])<=t[j]-t[i])
dp[j]=max(dp[j],dp[i]+);
}
for(int i=;i<=m;i++)
ans=max(ans,dp[i]);
///改变这里^^^^^^^^^^^^^^^^^
printf("%d",ans);
return ;
}
最新文章
- 事件event_scheduler
- 《轻量级Java Web整合开发入门SSH》 - 快速理解Java框架的又一积木
- 解决MVC4发布在IIS7后,路径无法访问.apk文件的解决方法
- bzoj3437 小P的牧场
- CentOS6.5系统挂载NTFS分区的移动硬盘 centos安装repoforge源(yum)
- Eclipse插件开发之基础篇(4) OSGi框架
- linux下top命令查看cpu占用情况
- STL标准模板库 向量容器(vector)
- Java-Android 之页面的跳转和结构的搭建
- Debug和Release之本质区别
- [js高手之路] html5 canvas教程 - 制作一个数码倒计时效果
- Tomcat 8.0的并发优化 - 优化server.xml的配置
- hikey960编译记录
- TLS1.3&;TLS1.2形式化分析
- [UE4]Spline Mesh Actor
- bui框架nav导航图标一览
- ESLint + lint-staged 禁用老项目中的es6
- 网络技术之TCP三次握手
- python 文件操作,os.path.walk()的回调函数打印文件名
- Substr函数助你免杀php脚本
热门文章
- Oracle 获取当前日期是月的第几周
- C++学习 之 继承方式(笔记)
- Android layout_marginBottom无效
- tp5.1中redis使用
- python_操作MySQL 初解 之__<;类方法调用并 增-删-改-查>;
- 简单的shell练习
- 什么是blazor
- Redis 高可用之哨兵模式(二)
- Http option 请求是怎么回事
- ubuntu18.04系统安装及php7.2,apache2,mysql8,git,svn,composer,vs code 到安装 php 扩展配置php.ini 实现 laravel5.8 运行