luogu P2285 [HNOI2004]打鼹鼠
2024-10-21 06:45:52
题目描述
鼹鼠是一种很喜欢挖洞的动物,但每过一定的时间,它还是喜欢把头探出到地面上来透透气的。根据这个特点阿牛编写了一个打鼹鼠的游戏:在一个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]就取max dp[I],dp[j]+1
#include<iostream>
#include<algorithm>
using namespace std; int t[],x[],y[],dp[];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&t[i],&x[i],&y[i]);
dp[i]=;
}
int ans=;
for(int i=;i<=m;i++)
{
for(int j=;j<i;j++)
{
if(abs(y[i]-y[j])+abs(x[i]-x[j])<=t[i]-t[j])
{
dp[i]=max(dp[i],dp[j]+);
}
}
ans=max(ans,dp[i]);
}
printf("%d\n",ans);
return ;
}
最新文章
- 遍历jsonobject
- 用CNTK搞深度学习 (二) 训练基于RNN的自然语言模型 ( language model )
- 调整label中text显示的行间距
- iproute-2.6.32
- 辛星浅谈PHP的混乱的编码风格
- spring mvc DispatcherServlet详解之三---request通过ModelAndView中获取View实例的过程
- 简单的BFS学习笔记
- JavaScript组成(三个组成部分)
- Web前端 web的学习之路
- 题解 P4783 【【模板】矩阵求逆】
- vscode垂直选中列选中
- kubernetes + istio进行流量管理
- [转帖]linux下的CPU、内存、IO、网络的压力测试
- 【LeetCode每天一题】Combinations(组合)
- 算法笔记 3.2 codeup1934 找X
- if else if else 语句
- Eureka Client的使用
- 【疑】checkpoint防火墙双链路切换导致丢包问题
- Oracle EBS OM 发放订单
- Guid ToString 格式