Oiclass P1221 题解

这道题不用多说也知道是 DP （看标签）

那么，究竟要怎样 DP 呢？下面依然是那熟悉的五步

1. 划分阶段

这里我采用的方法是划分爬到每一个位置，也就是以空间划分阶段

2. 确定状态和状态变量

OK，进入下一步 。在这里我定义的状态是在第 \(i\ (0<i≤n)\) 个位置时以跳到达和以爬到达的最优解，分别记为 \(jump_i\) 和 \(climb_i\)

3. 确定决策井写出状态转移方程

决策方式很简单，分以下两点

• 对于爬的方法，判断究竟以跳的方式到达上一层更快还是以爬的方式到达上一层更快，选择快的一种方式，并加上从上一层爬到此层所需的时间
• 对于跳的方法，我们只需要判断究竟从上一层跳过来更快还是从上上层跳过来更快，由于我们必须爬一层再跳，所以我们根本不需要考虑到达上一层或者上上层的方式，直接认为只有爬这一种方式即可，很简单对吧？

OK，分析完了，那么就把方程写出来吧，如下： \[ \begin{array}{lr} jump_i = \min(climb_{i-1},\ climb_{i-2})\\ climb_i=\min(climb_{i-1},\ jump_{i-1}) +a_i\ \ //a为输入的数列 \end{array} \]

4. 寻找边界条件

很容易发现，边界条件就是： \[ \begin{array}{lr} jump_1=0\\ climb_1=a_1 \end{array} \]

5. 实现

终于到了最激动人心的一步了（对于其他不是 DP 的题目），才怪，对于这道题，只需要按照分析模拟，最后判断究竟是爬的方法更快还是跳的方法更快，输出即可。代码如下：

#include <iostream>

using namespace std;

int n, a[10009], jump[10009], climb[10009];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    climb[1] = a[1];
    for (int i = 2; i <= n; i++) {
        climb[i] = min(climb[i - 1], jump[i - 1]) + a[i];
        jump[i] = min(climb[i - 1], climb[i - 2]);
    }
    cout << min(climb[n], jump[n]);
}