A6975 | [POI 2014] PTA-Little Bird

数据范围

样例解释

• 目标： 从第 1 棵树跳到第 9 棵树，每次跳跃距离 $\le 2$。
• 最优路径： $1 \to 3 \to 5 \to 7 \to 9$
1. $1 \to 3$ (高度 $4 \to 3$)：高度下降 ($4 3$)，花费 0。
2. $3 \to 5$ (高度 $3 \to 3$)：高度不降 ($3 \le 3$)，花费 1。
3. $5 \to 7$ (高度 $3 \to 2$)：高度下降 ($3 2$)，花费 0。
4. $7 \to 9$ (高度 $2 \to 5$)：高度上升 ($2 \le 5$)，花费 1。
• 总劳累值： $0 + 1 + 0 + 1 = \mathbf{2}$。

---

第二只鸟 ($k=5$)：
• 目标： 从第 1 棵树跳到第 9 棵树，每次跳跃距离 $\le 5$。
• 最优路径： $1 \to 6 \to 9$
1. $1 \to 6$ (高度 $4 \to 7$)：可以直接跳 (距离 5)，高度上升 ($4 \le 7$)，花费 1。
2. $6 \to 9$ (高度 $7 \to 5$)：可以直接跳 (距离 3)，高度下降 ($7 5$)，花费 0。
• 总劳累值： $1 + 0 = \mathbf{1}$。