蜗牛竹竿爬行

这天，一只蜗牛来到了二维坐标系的原点。

在 x 轴上长有 n 根竹竿。

它们平行于 y 轴，底部纵坐标为 00，横坐标分别为 x1,x2,…,xn。

竹竿的高度均为无限高，宽度可忽略。

蜗牛想要从原点走到第 n个竹竿的底部也就是坐标 (xn,0)。

它只能在 x 轴上或者竹竿上爬行，在 x 轴上爬行速度为 1 单位每秒；由于受到引力影响，蜗牛在竹竿上向上和向下爬行的速度分别为 0.7 单位每秒和 1.3 单位每秒。

为了快速到达目的地，它施展了魔法，在第 i和 i＋1 根竹竿之间建立了传送门（0<i<n），如果蜗牛位于第 i 根竹竿的高度为 ai 的位置 (xi,ai)，就可以瞬间到达第 i＋1根竹竿的高度为 bi+1 的位置 (xi+1,bi+1)，当然也可以选择不瞬移到第 i+1根竹竿。

请计算蜗牛最少需要多少秒才能到达目的地。

输入格式

输入共 1+n 行，第一行为一个正整数 n；

第二行为 n个正整数 x1,x2,…,xn；

后面 n−1行，每行两个正整数 ai,bi+1。

输出格式

输出共一行，一个浮点数表示答案（四舍五入保留两位小数)。

数据范围

对于 20%20% 的数据，保证 n≤15；

对于 100%100% 的数据，保证 1≤n≤10^5，1≤ai,bi≤10^4，1≤x1<x2<…<xn≤10^9。

输入样例：

1. 3
2. 1 10 11
3. 1 1
4. 2 1

输出样例：

4.20

样例解释

蜗牛路线：

(0,0)→(1,0)→(1,1)→(10,1)→(10,0)→(11,0)(0,0)→(1,0)→(1,1)→(10,1)→(10,0)→(11,0)，花费时间为 1+10.7+0+11.3+1≈4.20

思路：到达第i根竹竿时有多种方式，可以是（i-1,0）到（i，0），也可以是（i-1,1）到（i，1）在到（i,0)。有多种选择方式，故是贪心或者是dp算法，但因为每个方式都有可能产生最有解，所以这里是dp算法。

这里吧状态转移方程理清楚：

   for(int i=2;i<=n;i++)
    {
        int d=x[i]-x[i-1];
        f[i][0]=min(f[i-1][0]+d,f[i-1][1]+get(b[i-1],0)+d);
        f[i][1]=min(f[i-1][0]+a[i-1]/0.7,f[i-1][1]+get(b[i-1],a[i-1]));
    }

完整代码：

#include <iostream>
using namespace std;
#include <iomanip>
#include <algorithm>
const int N=100010,inf=2e9;
int a[N],b[N],x[N];
double f[N][2];
 
double get(int x1,int x2){
    if(x1>x2)return (x1-x2)/1.3;
    return (x2-x1)/0.7;
}
int main(){
    int n;
    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=0;i<=n;i++)f[i][0]=f[i][1]=inf;
    f[1][0]=x[1];
    for(int i=2;i<=n;i++)
    {
        int d=x[i]-x[i-1];
        f[i][0]=min(f[i-1][0]+d,f[i-1][1]+get(b[i-1],0)+d);
        f[i][1]=min(f[i-1][0]+a[i-1]/0.7,f[i-1][1]+get(b[i-1],a[i-1]));
    }
    cout<<setiosflags(ios::fixed)<<setiosflags(ios::right)<<setprecision(2)<<min(f[n][1]+b[n]/1.3,f[n][0]);
}