2024寒假每日一题全部题解传送门>>

根据题意，蜗牛经过一个竹竿有两种选择方式，一种是直接从竹竿底部走过去，另一种是经过当前的传送门传送到下一个竹竿的某个位置，不妨将这两种选择看作成是两种状态$0$和$1$，$0$表示不经过当前竹竿的传送门，$1$表示经过当前竹竿的传送门。那么根据闫氏DP分析法，定义一个状态集合$f[i][j]$表示蜗牛位于第$i$根竹竿的第$j$种状态所花费的时间，集合属性即求最小值。而题目中只有两种状态，故$j$的取值为$0$和$1$。

分析完集合和属性，那么关键之处就在于如何进行状态计算了。而对于每个集合$f[i][j]$，发现都可以从$f[i-1][0]$和$f[i-1][1]$两种状态转移过来，故只要求这两种转移状态的最小值即可。

首先来分析$f[i][0]$的状态转移方程：
$f[i][0]$表示到第$i$根竹竿的底部
1. 可以从上一个竹竿的底部转移过来，即：
$f[i][0]=f[i-1][0]+x[i]-x[i-1]$。
2. 也可以从上一个竹竿的传送门转移过来，即：
$f[i][0]=f[i-1][1]+b[i-1]/1.3$。

再来分析$f[i][1]$的状态转移方程：
$f[i][1]$表示到第$i$根竹竿的传送门处
1. 可以从上一个竹竿的底部转移过来，即：
$f[i][1]=f[i-1][0]+x[i]-x[i-1]+a[i]/0.7$。
由于$f[i][0]=f[i-1][0]+x[i]-x[i-1]$，故可以简化为$f[i][1]=f[i][0]+a[i]/0.7$。
2. 也可以从上一个竹竿的传送门转移过来，但此时有一个注意的地方，要判断蜗牛经过上一根竹竿的传送门后到达下一根竹竿的传送门的上方还是下方。如果在传送门的下方，蜗牛就要向上走到达当前竹竿的传送门；如果在传送门的上方，那么蜗牛就要向下走到达当前竹竿的传送门。
如果在当前传送门的下方：$f[i][1]=f[i-1][1]+(a[i]-b[i-1])/0.7$。
如果在当前传送门的上方：$f[i][1]=f[i-1][1]+(b[i-1]-a[i])/1.3$。
即$f[i][1]=f[i-1][1]+abs(a[i]-b[i-1])/(b[i-1]$$\geq$$a[i]?1.3:0.7)$。

综上所述：
$f[i][0]=min(f[i-1][0]+x[i]-x[i-1], f[i-1][1]+b[i-1]/1.3)$。
$f[i][1]=min(f[i][0]+a[i]/0.7,f[i-1][1]+abs(a[i]-b[i-1])/(b[i-1]$$\geq$$a[i]?1.3:0.7))$。

由于题目是要求到达第$n$根竹竿底部花费的最少时间，那么答案就是$f[n][0]$。

C++代码：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e5 + 10;
int x[N], a[N], b[N];
double f[N][2];
int n;

int main()
{
    scanf("%d", &n);

    for(int i = 1; i <= n; i ++) scanf("%d", &x[i]);
    for(int i = 1; i < n; i ++) scanf("%d%d", &a[i], &b[i]);

    memset(f, 0x7f, sizeof f); // 因为是求最小值，所以先把所有集合初始化成无穷大

    f[1][0] = x[1]; f[1][1] = a[1] / 0.7 + x[1]; // 初始化
    for(int i = 2; i <= n; i ++)
    {
        // 四种状态转移方程
        f[i][0] = f[i - 1][0] + x[i] - x[i - 1];
        f[i][0] = min(f[i][0], f[i - 1][1] + b[i - 1] / 1.3);
        f[i][1] = f[i][0] + a[i] / 0.7;
        f[i][1] = min(f[i][1], f[i - 1][1] + abs(b[i - 1] - a[i]) / (b[i - 1] >= a[i] ? 1.3 : 0.7));
    }

    printf("%.2lf", f[n][0]);
    return 0;
}