Skip to content

11995: 【原1995】二哥的猫

题目

题目描述

author: Weihao Kong 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1995

题目描述

二哥平时生活非常勤俭,从来只吃外卖不吃食堂。某日,好心的二哥收养了一只流浪猫,但是猫咪对二哥糟糕的伙食状况非常不满,屡次想要偷吃二哥的鸟改善生活。于是二哥想到放猫咪去食堂蹭饭,但是去食堂的路上有许多凶悍的野狗巡逻把守,直接去恐怕有来无回,当然这也难不倒聪明的二哥,二哥给猫咪做了一个外面画着老虎的盒子。这样猫咪可以在野狗经过的时候趴下休息,用盒子把自己保护起来。待危险解除后继续前行。同时由于经过了充分的休息,可以获得一定的能量点数,猫咪可以选择进行一次长达数米的跳跃。现在二哥想知道猫咪最少需要多长时间可以到达食堂。

开始时,猫咪在坐标\(0\)点出发,初始能量为\(0\),食堂的坐标为\(D\)米,猫咪的前进速度为\(1\)米/秒。每一秒,猫咪可以选择原地休息(能量点加\(1\))或前进\(1\)米或进行一次跳跃(前进\(K\)米,消耗\(K-1\)点能量,当然前提是当前拥有至少\(K-1\)点能量)。每一只野狗也在开始时同时出现,其属性包括出现时的坐标,前进速度,视野范围(可以同时向前和向后看)。每只野狗的前进方向都是坐标轴负方向。猫咪必须完全在狗的视野范围之外才能行动。

输入格式

输入共有两行。

第1行有2个整数,分别表示食堂的位置\(D\)野狗的个数\(n\)。

接下来有n行,每行有3个整数,表示一只野狗的出现位置,前进速度,视野范围。

保证野狗出现的位置小于\(2D))。

输出格式

输出一个整数\(t\),表示猫咪到达食堂的最短时间。

说明

对于全部数据:食堂的位置\(1 \leq D \leq 10000\)。 野狗的个数\(0 \leq n \leq 2000\)。

样例输入

10
3
18 2 1
3 2 1
8 1 2

样例输出

11

样例解释:

第1秒中,猫咪不能前进,否则会被2号野狗发现。这一秒结束时能量:1

第2秒中,猫咪不能前进,否则会被2号野狗发现。这一秒结束时能量:2

第3秒中,猫咪不能前进,否则会被2号野狗发现。这一秒结束时能量:3

第4秒中,猫咪前进1米,此时不可以选择跳跃,否则会被3号野狗发现。这一秒结束时能量:3

第5秒中,猫咪不能前进,否则会被3号野狗发现。这一秒结束时能量:4

第6秒中,猫咪不能前进,否则会被3号野狗发现。这一秒结束时能量:5

第7秒中,猫咪不能前进,否则会被3号野狗发现。这一秒结束时能量:6

第8秒中,猫咪不能前进,否则会被3号,1号野狗发现。这一秒结束时能量:7

第9秒中,猫咪不能前进,否则会与3号,1号野狗发现。这一秒结束时能量:8

第10秒中,猫咪不能前进,否则会被3号,1号野狗发现。这一秒结束时能量:9

第11秒中,猫咪选择跳跃,直接到达食堂。这一秒结束时,猫到达食堂,能量:1

判断在\(x\)位置的猫,前进\(t\)米,是否会被位置为\(y\),速度为\(a\),视野为\(b\)的狗发现的依据是 \([x,x+t]\)与\([y-a-b,y+b]\)的交是否为空集。

限制

时间限制:1000ms,内存限制:65536kb

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!