Description 桐桐一直有个梦想，很希望像“蜘蛛人”罗伯特一样飞檐走壁。为了达成这个梦想，桐桐每天都辛勤练习攀爬。练习的出发点与终点都是在地上面。给出一个数列，代表她每次移动的距离。这个移动可以向上，也可以向下。但是不可能到达地下面去的。而她做练习使用的建筑物总是比她到达过的最高位置高 2 米。现在我们希望这个建筑物的高度越小越好。 如：20 20 20 20 如果是上，上，下，下的话，这个建筑物就要 42 米高，如果是上，下，上，下，就只要 22 米高。 当然有些数列是无解的，例如：3421645。 Format Input 第 1 行输入 n（n ≤ 100），代表有 n 个爬行距离； 第 2 行输入 n 个爬行距离（均为整数），这些爬行距离的总和不超过 10000。 Output 如果有解，则输出最小的高度； 否则输出“IMPOSSIBLE”。 Samples 输入数据 1 4 20 20 20 20 输出数据 1 22 要求:给出详细注释的代码

解题思路：

这道题可以用动态规划来解决。设 $f_{i,j}$ 表示考虑前 $i$ 个移动距离，最高点为 $j$ 时，建筑物的最小高度。则转移方程为：

$$ f_{i,j} = \min(f_{i-1,j+d_i}, f_{i-1,j-d_i}) $$

其中 $d_i$ 表示第 $i$ 次移动的距离。

需要注意的是，最高点不能超过当前已经到达的最高点加上 $2$ 米，即 $j \leq \max_{k=1}^i \sum_{l=1}^k d_l + 2$。

初始化时，$f_{0,0}=0$，其余为正无穷。

最终答案为 $\min_{j=0}^{\max_{k=1}^n \sum_{l=1}^k d_l + 2} f_{n,j}$。

如果最终答案为正无穷，则输出 "IMPOSSIBLE"。

代码如下：

相关问题

Description 桐桐一直有个梦想，很希望像“蜘蛛人”罗伯特一样飞檐走壁。为了达成这个梦想，桐桐每天都辛勤练习攀爬。练习的出发点与终点都是在地上面。给出一个数列，代表她每次移动的距离。这个移动可以向上，也可以向下。但是不可能到达地下面去的。而她做练习使用的建筑物总是比她到达过的最高位置高 2 米。现在我们希望这个建筑物的高度越小越好。 如：20 20 20 20 如果是上，上，下，下的话，这个建筑物就要 42 米高，如果是上，下，上，下，就只要 22 米高。 当然有些数列是无解的，例如：3421645。 Format Input 第 1 行输入 n（n ≤ 100），代表有 n 个爬行距离； 第 2 行输入 n 个爬行距离（均为整数），这些爬行距离的总和不超过 10000。 Output 如果有解，则输出最小的高度； 否则输出“IMPOSSIBLE”。

Solution 思路

本题是一道非常典型的模拟题。我们可以根据题目所述的条件，模拟出桐桐爬行的过程，并且计算出建筑物的高度，最后输出最小的建筑物高度。

做题的时候，可以设置一个变量 $height$ ，表示桐桐爬行过程中到达的最高高度，同时也可以在模拟的过程中计算出建筑物的高度。每当桐桐爬到一个新的位置时，我们需要判断她是向上还是向下爬行，然后根据她目前到达的最高高度，来判断是否需要更新建筑物的高度。

如果最后建筑物的高度仍然比桐桐到达过的最高高度低 2 米，那么这个高度就是最小的建筑物高度。否则，无解。

Time Complexity

时间复杂度为 $O(n)$。

Space Complexity

空间复杂度为 $O(1)$。

参考代码