Oiclass P1220 题解

从标签题面可以看出这是一道动规（DP）

进入正题，依旧是传统的五步

1. 划分阶段

这里我的思路是将每公里的数值作为一个阶段，即 \(n\) 公里就有 \(n\) 个阶段，分别是: \[ 1, 2, 3, 4, 5, 6 ....(n-2),(n-1),(n) \]

2. 确定状态和状态变量

这里使用一个数组 \(f\) 来保存状态，即第 \(i\) 个状态为 \(f_i\) ，然后就没有了

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

我们观察可以发现，对于一个状态 \(f_i\) 他将由 \(f_{i-?} 与 \large {a}_?\) 组成，那么"?" 究竟是什么呢？不难发现，？可以是 \(1\to10\) 的任意一个值，那么我们在这里就可以枚举 ？所代表的值，然后对这些计算出来的状态取最小值，也就是求他们的 \(\min\) 值。思路清晰了，就可以动手写出状态转移方程了，如下 \[ f_i=\min\left (\min_{j=i-1\ ,\ j--}^{j>(i-10)} f_j+a_{i-j},\ f_i\right) \] 但是这个方程也有特例，仔细看不难看出，\(j ≤ 0\) 也是有可能的，对于数学，这没有问题，但是来到计算机上，数组下标为负是万万不可以的，所以，我们需要特判一下，也就是说当 \(j ≤ 0\) 的时候，我们的 \(f_i = a_i\) 并将其计入 \(\min\) 的范围，修改后如下 \[ f_i=\min\left (\min_{j=i-1\ ,\ j--}^{j\ >\ (i-10)\ \&\&\ j\ >\ 0} f_j+a_{i-j},\ f_i,\ a_i\right) \] OK，复杂的方程写完了，下面的就很简单了

4. 寻找边界条件

边界条件很简单，\(f_1 = a_1\)

5. 实现

直接模拟，如下：

#include <iostream>
#include <cstring>

using namespace std;

int a[12], f[200], n;

int main() {
    for (int i = 1; i <= 10; i++) {
        cin >> a[i];
    }
    cin >> n;
    memset(f, 127, sizeof f);
    f[1] = a[1];
    for (int i = 2; i <= n; i++) {
        for (int j = i - 1; j >= i - 10; j--) {
            if (j <= 0) {
                f[i] = min(f[i], a[i]);
            } else {
                f[i] = min(f[i], f[j] + a[i - j]);
            }
        }
    }
    cout << f[n];
}