[题解]P2800-又上锁妖塔

Clu3ter · 2019-07-14 11:37:56 · 题解

这道题是一道DP题。

描述状态f[i]表示到达第i层之上所用的最短时间。

初始状态即为塔底，根本不需要时间。 那么 边界条件 就很明显了：

接着，题目要求的是到达塔外的时间，而塔有n层，所以最终要求的解的就是

然后我们自己搞一组数据：

INPUT：

6
5 2 4 5 3 2

OUTPUT:

5

我们把这组数据画下来：

塔底f[0]=0，解是f[7]

不难看出，这组数据的走法是：

(\rightarrow表示爬，\Rightarrow表示仙术瞬移)

接下来我们来推导

状态转移方程

根据题意，到达第i楼有三种方法：

1. 徒步爬楼（花费与下层层高相等的时间 a[i-1]）
2. 仙术瞬移1层（不花费时间 0）
3. 仙术瞬移2层（不花费时间 0）

也有限制条件：

仙术瞬移无法连续使用

那么也就是说，仙术瞬移之后必须爬楼，爬楼是世间万物の归宿，是不可避の物，是死亡の灯塔，是宇宙の终结，则爬楼到达第i楼的三种方法有所变化：

1. 从i-1楼徒步爬楼.

   （ 花费时间 a[i-1] \quad|\quad 总花费时间 f[i-1]+a[i-1] ）

2. 从i-2楼仙术先瞬移1层到i-1楼，再徒步爬楼.

   （ 花费时间 a[i-1] \quad|\quad 总花费时间 f[i-2]+a[i-1] ）

3. 从i-3楼仙术先瞬移2层到i-1楼，再徒步爬楼.

   （ 花费时间 a[i-1] \quad|\quad 总花费时间 f[i-3]+a[i-1] ）

如下图

这样的话，就不需要考虑仙术不能连续使用的问题了，

所以，到达第i层所需要的最短时间f[i]，就是三种方法所需要总时间中的最小值，于是我们成功推导出了状态转移方程：

下面奉上蒟蒻的辣鸡代码，还请垂阅敝码，多多赐教

#include<bits/stdc++.h>
using namespace std;

int n;
int a[1000005];
int f[1000005];

int main() {
    cin>>n;
    for(int i=1; i<=n; i++) {
        cin>>a[i];
        f[i]=1e9;//注意初始化
    }
    f[n+1]=1e9;

    for(int i=1; i<=n+1; i++) {//循环到n+1
        f[i]=min(f[i],f[i-1]);
        f[i]=min(f[i],f[i-2]);
        f[i]=min(f[i],f[i-3]);
        f[i]+=a[i];
    }

    cout<<f[n+1];//输出解
    return 0;//愉快的结束
}

文明查题解，拒绝复制粘贴

『做正确，好懂，好看的题解』