luogu#P11147. 「SFMOI Round I」Strange Dino Game

    ID: 15072 远端评测题 3000ms 512MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>模拟动态规划,dp贪心二分洛谷原创O2优化洛谷月赛

「SFMOI Round I」Strange Dino Game

题目背景

English statement. You must submit your code at the Chinese version of the statement.

Watersphere 同学在家没网了,只好玩起了 dino 游戏,但是他很菜,一玩到后面就头晕眼花,所以想让你编个程序帮助他拿到更高分,于是有了这题。

本题的游戏背景是 Dino。可以考虑点击链接游玩,以便更好理解题意。

题目描述

我们将问题放在二维平面上描述。我们给出一些游戏要素:

  • 玩家:Dino。可以将其视为一个点。
  • 障碍物:
    • 仙人掌:形如 (xi,0),(xi,hi)(x_i',0),(x_i',h_i) 的线段。
    • 飞鸟:形如 (xi,di),(xi,ui)(x_i,d_i),(x_i,u_i) 的线段。
  • 游戏结束:Dino 与障碍物上的任意一点(包括线段端点)重合时,游戏结束。
  • 起点:原点 (0,0)(0,0)
  • 终点:使游戏结束的位置,位于第一象限(或 xx 轴上)。可能不存在(即游戏能无限进行)。
  • 游戏分数:终点的 xx 坐标。终点不存在时定义为无穷大。
  • 跳跃参数:正整数 d,hd,h
  • 步行:Dino 在 xx 轴上沿着 xx 轴正方向移动。
  • 跳跃:当 Dino 在 xx 轴上时,可以进行一次跳跃。以起跳点为原点,跳跃轨迹为$$f(x) = \begin{cases} \displaystyle \frac{h}{d}x & x\in [0, d) \\ \displaystyle-\frac{h}{d}x+2h & x\in [d, 2d) \\ \end{cases}$$
    • 需要注意的是,由上述定义可以推出:在一次跳跃后落地的瞬间进行第二次跳跃是合法的。
    • 需要注意的是,可以在任意实数点(只要在 xx 轴上)处开始跳跃。也就是说,跳跃不一定在整点开始。

下图展示了 d=2,h=6d=2,h=6 时的一次跳跃。

在一局游戏中,Dino 从起点出发向 xx 轴正方向移动。目标是最大化得分,即尽量避开障碍物,使自己移动的距离尽量长。

每一时刻,Dino 只能做一件事:步行,或跳跃。当且仅当 Dino 在 xx 轴上时可以进行跳跃。

形式化地说,Dino 的行为可以被描述为一个长度为 (k+1)(k+1) 的实数二元组序列 [(x0,t0),(x1,t1),,(xk,tk)][(x_0,t_0),(x_1,t_1),\cdots,(x_k,t_k)],满足:

  • x0=0x_0=0
  • ti{0,1}t_i\in \{0,1\}
  • 0i<k\forall 0\le i\lt k, xi<xi+1x_i\lt x_{i+1}
  • ti=1,i<k    xi+1xi2dt_i=1,i\lt k\implies x_{i+1}-x_i\ge 2d;(二段跳是不允许的)
  • 0i<k\forall 0\le i\lt k, ti=ti+1    ti=ti+1=1t_i=t_{i+1}\implies t_i=t_{i+1}=1

ti=0t_i=0 时,我们定义 Dino 在 xix_i 进入步行状态,否则定义 Dino 在 xix_i 进入跳跃状态

当 Dino 与障碍物重合时,游戏结束。此时 Dino 在的位置为终点,得分为终点的 xx 坐标。

已知有 bb 只飞鸟和 cc 个仙人掌,求出 Dino 的最大得分。特别地,得分可以为无穷大。

可参阅样例解释的图片。

输入格式

本题单个测试点内有多组测试数据。

第一行,一个正整数 TT,代表游戏次数。

接下来依次描述 TT 组数据:

  • 每组数据第一行,两个正整数 d,hd,h,表示 dino 的跳跃参数。
  • 每组数据第二行,两个整数 b,cb,c,表示飞鸟个数与仙人掌个数。
  • 接下来 bb 行,每行三个正整数 xi,ui,dix_{i},u_i,d_i,描述第 ii 只飞鸟。
  • 接下来 cc 行,每行两个正整数 xi,hix'_{i},h_{i},描述第 ii 株仙人掌。

输出格式

对于每组数据输出一行,表示得分的最大值。

特别地,如果得分为正无穷,输出 Dino!

2
1 3
1 2
1 2 1
2 2
3 2
1000000000 1000000000
1 0
114514 1919 810
3
Dino!
1
8 16
8 3
5 18 13
4 20 10
6 13 1
2 17 11
1 11 6
5 1 1
2 6 3
1 16 1
7 20
7 13
3 2
6
1
5 5
1 2
5 5 1
6 1
16 3
16
1
5 5
1 4
19 10 8
4 1
15 1
22 2
20 1
22

提示

样例 11 解释:

  • 对于第 11 组数据,dino 无论如何也无法跳过连续的两株高为 22 的仙人掌,答案即为第二株仙人掌的 xx 轴坐标。
  • 对于第 22 组数据,dino 可以在原点直接起跳跳过唯一的一只鸟,也完全可以不起跳从飞鸟下方走过。

其中第一组数据的解释如下所示,红线代表飞鸟,绿线代表仙人掌,粉线代表 Dino 的轨迹。

数据范围

本题采用捆绑测试。

  • Subtask 1(5 pts):c=0c=0
  • Subtask 2(5 pts):b,c10b,c \le 10
  • Subtask 3(20 pts):b=0b=0
  • Subtask 4(20 pts):1d,h,xbi,di,ui,xi,hi1051 \le d,h,x_{b_i},d_i,u_i,x_i',h_i \le 10^5;
  • Subtask 5(40 pts):无特殊限制。
  • Subtask 6(10 pts):无特殊限制。

对于 100%100\% 的数据,保证:

  • 1T101 \le T \le 10
  • 0b,c2×1040 \le b,c \le 2\times 10^4
  • 1d,h,xbi,di,ui,xi,hi1091 \le d,h,x_{b_i},d_i,u_i,x_i',h_i\le 10^9
  • diuid_i\le u_i