【Coding】寒假每日一题Day.4. 蜗牛

题目来源

题目来自于AcWing平台：https://www.acwing.com/problem/content/5403/
以blog的形式记录程序设计算法学习的过程，仅做学习记录之用。

题目表述

输入输出格式与数据范围

样例

3
1 10 11
1 1
2 1

4.20

思路

思路参考自闫总的视频讲解和代码。

刚开始看到这道题的时候，其实没有看出来这是一道DP的问题。看了闫总的视频讲解，其中闫总提到，贪心和DP的区别在于，对于每一步决策产生的两个集合，如果最优解只存在于单个集合当中，那么这是一个贪心问题，否则就是一个DP的问题，受益匪浅。显然，对于这道题目，蜗牛的爬行方式有两种，即横着一直爬，或是先向上爬再瞬移再向下爬，最优解显然同时存在于两个集合当中，应当使用DP来进行求解。

DP的重点就在于定义状态，并求状态转移方程。那么蜗牛的状态应当如何定义呢？显然不能将蜗牛在每一个位置的状态都进行定义，那就是无穷多种，无法求这么多情况，于是可以看寻找状态的临界点。

何为临界点？回到题目描述，其中提到，最后要求的是蜗牛从原点$(0,0)$，一直爬到第$n$根竹竿底部的坐标$(x_n,0)$最少需要花费多少秒。显然我们可以将这个临界点就定义为蜗牛到达$(x_i,0)$即第$i$根竹竿底部需要多少秒。这样就将无穷多种情况减少到了两种情况，即蜗牛只有可能从第$i?1$根竹竿底部一路沿着$x$轴爬到当前竹竿的底部，或是它使用了瞬移，首先到达了第$i?1$根竹竿的$b[i?1]$位置，再一路爬下来到达第$i?1$根竹竿底部，再沿着$x$轴爬过来。（这个思路参考自闫总的视频讲解，但我认为，如果将“使用了瞬移”的状态定义为从前面的竹竿瞬移到了$b[i]$，再直接向下爬到底部，直接到达第$i$根竹竿的底部应该也是可以的）

由此，状态转移方程需要维护两个状态，使用二维数组$f[maxn][2]$进行保存，$f[i][0]$表示的状态是达到第$i$根竹竿底部所需要的时间，$f[i][1]$ 表示的状态是到达第$i$根竹竿的$b[i]$位置所需要的时间。

首先计算$f[i][0]$，根据上述分析，显然产生这一状态有两种可能，即从第$i?1$根竹竿底部一路沿着$x$轴爬过来，或是先到达$i?1$的$b[i?1]$再向下、向右爬过来，即： f [ i ] [ 0 ] = min ? { f [ i ? 1 ] [ 0 ] + d , f [ i ? 1 ] [ 1 ] + g e t ( b [ i ? 1 ] , 0 ) + d } f[i][0] = \min\{f[i-1][0]+d, f[i-1][1]+get(b[i-1], 0)+d\} f[i][0]=min{f[i?1][0]+d,f[i?1][1]+get(b[i?1],0)+d}，其中$d$表示的是两根竹竿之间的距离，使用函数$get$来求在竹竿上向上爬或是向下爬所需要的时间；

再计算$f[i][1]$，显然它也有两种可能，但是我们首先需要知道，它存储的就是通过“瞬移”到达$b[i]$的状态，即它存储的就是到达$i?1$根竹竿的第$a[i?1]$位置的所有情况，分为两种：第一种是从$i?1$根竹竿底部一路爬上来到$a[i?1]$，从而瞬移到$b[i]$；第二种是从$i?2$根竹竿先瞬移到$i?1$的$b[i?1]$位置，再爬到$a[i?1]$进行瞬移。

有了上述分析，就可以动手编码来解决这道题了。

Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>
using namespace std;

const int maxn = 1e5 + 5, INF = 2e9+5;
int a[maxn] = {0}, b[maxn] = {0}, x[maxn] = {0};
double f[maxn][2];

int n;

double get(int x1, int x2){
    if(x1 > x2) return (x1-x2)/0.7;
    else        return (x1-x2)/1.3;
}

int main()
{
    // 为什么要使用DP，可以看到，每一步的选择
    // 有两种集合，即往上走或往下走，最优解同
    // 时在这两个集合里，因此需要使用DP。
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> x[i];
    }
    for(int i=1;i<n;i++){
        cin >> a[i] >> b[i+1];
    }
    for(int i=1;i<=n;i++){
        f[i][0] = f[i][1] = INF;
    }

    // 👆输入与初始化，现在开始进行DP👇
    f[1][0] = x[1];
    for(int i=2;i<=n;i++){
        int d = x[i] - x[i-1];
        // 使用f[i][0]来维护爬到第i个竹竿纵坐标为0位置的情况
        // 使用f[i][1]来维护爬到第i个竹竿纵坐标位置为b[i]的情况
        f[i][0] = min(
            f[i-1][0] + d,  // 即从上一个竹竿底部沿着x轴爬过来
            f[i-1][1] + get(b[i-1], 0) + d  // 从上一根竹竿的
            // b[i-1]位置先爬下来，再沿着x轴横着爬过来
        );
        f[i][1] = min(
            f[i-1][0] + get(0, a[i-1]), // 使用了瞬移，从上一根竹竿底部
            // 爬到上一根竹竿的第a[i-1]位置，从而瞬移到了b[i]位置
            f[i-1][1] + get(b[i-1], a[i-1]) // 同样使用了瞬移，但是起点
            // 不是上一根竹竿的底部，因为可能到达上一根竹竿也是从再上一根
            // 竹竿瞬移过来的，从再上一根竹竿瞬移到b[i-1]的位置，需要先爬
            // 到a[i-1]的位置，才能瞬移到b[i]的位置。使用get函数判断是向
            // 上爬还是向下爬。
        );
    }
    cout<<fixed<<setprecision(2)<<min(f[n][0], f[n][1] + b[n]/1.3);
    return 0;
}