xehoth / xehoth-blog-comment

0 stars 0 forks source link

「CC JUMP」Jump mission-DP + 动态凸包 + 树状数组 | xehoth #332

Open xehoth opened 6 years ago

xehoth commented 6 years ago

https://blog.xehoth.cc/CC-JUMP-Jump-mission/

有 $N$ 座山排成一排,每座山都有一个 $1 \sim N$ 的唯一编号。第 $i$ 座山的编号为 $P_i$,高度为 $H_i$。大厨从第一座山出发,目标是到达第 $N$ 座山。他可以从第 $i$ 座山跳到第 $j$ 座山上($i < j, P_i < P_j$),并花费 $(H_i - H_j) ^ 2$ 的能量,当大厨处于第 $i$ 座山时,他还会花费 $A_i$ 的能量($A