轻松爬山 Easy Climb
题意翻译
### 题目描述
某地周围环绕着巍峨的群山。但有一个问题:爬山是非常困难的,因为它们有相当大的高度差。为了使更多的人能够爬山并享受风景,我们想让爬山更容易些。
为此,我们将对山进行如下改造:山由 $n$ 堆相邻的石头组成,每一堆都有高度 $h_i$ 。相邻山的高度差为 $h_{i+1} - h_i$ ($1 \le i \le n-1$)。我们希望这些高度差的绝对值小于或等 $d$ 。
我们可以通过增加或减少每一堆石头高度来实现这一点。第一堆(起点)和最后一堆(终点)的高度应保持不变。由于添加和移除石头需要费很大的力,我们希望添加的石头数加上移除的石头数的总数最小。这个最小值是多少?
### Input
在第一行有一个正数:表示测试数据的数量,至多为100。每组测试数据都包含:
•一行两个整数 $n$ ($2 \le n \le 100$)和 $d$ ($0 \le d \le 10^9$):石头堆的数量以及允许的最大高度差。
•一行 $n$ 个整数 $h_i$ ($0 \le h_i \le 10^9$):第 $i$ 堆石头的高度。
### Output
对于每组测试数据:
•每行输出必须添加和移除的最小石头总数量。若不可能达到目标,则输出“impossible”。
题目描述
[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=243&page=show_problem&problem=3322
[PDF](https://uva.onlinejudge.org/external/121/p12170.pdf)
![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA12170/b72bba61bc9ea7e086d38d2165aff1f53663d567.png)
输入输出格式
输入格式
![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA12170/9fa6cce6a8ce12d554ca10633d91f098fd8e56a6.png)
输出格式
![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA12170/9cf43f1387d790efcfbc435b7605e22bb9fc6bae.png)
输入输出样例
输入样例 #1
3
10 2
4 5 10 6 6 9 4 7 9 8
3 1
6 4 0
4 2
3 0 6 3
输出样例 #1
6
impossible
4