Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom1月前

05/17
20:35
一般动规与递推

[bzoj 4884] [Lydsy2017年5月月赛]太空猫

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

太空猫(SpaceCat)是一款画面精致、玩法有趣的休闲游戏,你需要控制一只坐在迷你飞碟上的猫咪在太空里不断探索,让大家看看你能飞得多远。游戏地图可以看成一个二维的网格图,上下是两段障碍物。在游戏的一开始,太空猫位于地图最左边的下边界之上,且重力方向向下。
在每个时刻,你可以用手指点击屏幕,翻转重力的方向,或者通过遥感控制太空猫往左或往右移动。每次翻转重力方向时,你需要消耗的能量值等于上下底边之间的高度差。在左右移动的时候,太空猫可以下降到对应重力方向更低的位置,但不能往上爬。当然,太空猫也不能穿墙而过。在重力翻转的过程中,直到碰到地面之前,你都不能操控太空猫左右移动。太空猫的终点位于地图的最右端的下底边之上,请计算为了让太空猫到达终点,需要消耗能量的最小值。

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

第一行包含一个正整数n(1<=n<=100000),即地图的宽度。
第二行包含n个正整数c_1,c_2,...,c_n(2<=c_i<=10^9),分别表示每个横坐标对应的上边界的高度。
第三行包含n个正整数f_1,f_2,...,f_n(1<=f_i<c_i),分别表示每个横坐标对应的下边界的高度。

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

输出一行一个整数,即最少的能量,若无法到达终点,请输出“-1”。

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

4
3 4 3 2
1 2 1 1

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

4

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

“在左右移动的时候,太空猫【可以】下降到对应重力方向更低的位置”

应改为 “太空猫【会】下降到对应重力方向更低的位置”
就是说,太空猫在能往下掉的时候不能选择直接飞过去

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

f[i][0/1]表示在第i个位置上面/下面所需要的最小花费,直接dp

 

[bzoj 4884] [Lydsy2017年5月月赛]太空猫