题解 | #小红的悬崖#

对于悬崖上连续的三个点，它们构成的形状可以分为两类：“<”形（高点与低点的连线不穿过悬崖）与 “>”形。
（高点与低点的连线穿过了悬崖）
对于“>”形，从顶端到达底端的最短路径就是顺着形状走，而对于“<”形状，从顶端到达底端的最短路径可以忽
略中间的点，即顶端到底端的连线。
所以最短的路径应当是许多“>”形组成的形状，并且只要构成了这种形状，那么在路径中任取三个点，它们构成
的也都是“>”形。
假设我们已经求出了一条从0到i的最短路径a[0...j],那么从0到i+1的最短路径只需要考虑a[j-1]、a[j]与
i+1三个点所构成的形状。若为“>”形，则为最短路径;若为“<”形，则点a[j]是可以忽略的，此时则要考察点
a[j-2]与a[j-1]和i+1三个点构成的关系，直到满足“>”形。

```#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
int n;
int A[100010][2];
signed main()
{

    cin>>n;
    for(int i = n ; i >=0 ;i--)
    {
        cin>>A[i][0];
        A[i][1]=n-i;
    }
    
    vector<int> B;
    B.reserve(n);
    for(int i = 0 ; i < n+1 ;i++)
    {
        if(B.size() < 2)
        {
            B.push_back(i);
            continue;
        }
        int l2 = B[B.size()-1];
        int l1 = B[B.size()-2];
        if( (double)(A[l2][1]-A[i][1])*(A[l1][0]-A[i][0]) >= (double)(A[l2][0]-A[i][0])*(A[l1][1]-A[i][1]))
        {
            B.pop_back();
            i--;
        }
        else
            B.push_back(i);
    }
    long double sum = 0;
    for(unsigned int i = 1; i < B.size(); i++)
        sum += sqrt(pow((A[ B[i] ][1]-A[ B[i-1] ][1]),2) + pow((A[ B[i] ][0]-A[ B[i-1] ][0]),2));
    printf("%.9Lf",sum);
    
    return 0;
}