斜率dp cdq 分治

f[i] = min { f[j] + sqr(a[i] - a[j]) }

f[i]= min { -2 * a[i] * a[j] + a[j] * a[j] + f[j] } + a[i] * a[i]

由于a[i]不是单调递增的，不能直接斜率dp。

考虑有cdq分治来做，复杂度(nlog2n)

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 using namespace std;

 #define maxn 100008

 #define LL long long

 long long f[maxn];

 int a[maxn],b[maxn];

 int n;

 bool flag=;

 void read(int &x){

     char ch;

     for (ch=getchar();ch<''||ch>'';ch=getchar()); x=ch-;

     for (ch=getchar();ch>=''&&ch<='';ch=getchar()) x=x*+ch-;

 }

 void init(){

     read(n);

     for (int i=;i<=n;i++) { read(a[i]); read(b[i]); if (b[i]) flag=; }

     for (int i=;i<=n;i++) f[i]=(LL)<<;

 }

 void force(){

     for (int i=;i<=n;i++)

         for (int j=;j<=i-;j++)

             if (a[j]>=b[i])

                 f[i]=min(f[i],f[j]+(LL)(a[i]-a[j])*(a[i]-a[j]));

 }

  int q[maxn],rk[maxn];

 bool cmp(int i,int j){

     return a[i]<a[j] ;

 }

 long long kx(int i,int j){

     return *(a[i]-a[j]);

 }

 long long ky(int i,int j){

     long long ans=1LL*a[i]*a[i]+f[i]-1LL*a[j]*a[j]-f[j];

     return ans;

 }

 bool cmp1(int i,int j,int k){

     return ky(k,j)*kx(j,i)<=kx(k,j)*ky(j,i);

 }

 bool cmp2(int i,int j,int k){

     return ky(i,j)>=k*kx(i,j);

 }

  void solve(int l,int r){

     if (l==r) return;

     int mid=(l+r)>>;

     solve(l,mid);

     for (int i=l;i<=r;i++) rk[i]=i;

     sort(rk+l,rk+r+,cmp);

     int h=,t=;

     for (int i=l;i<=r;i++)

     {

         if (rk[i]<=mid) {

             while (h<t&&cmp1(q[t-],q[t],rk[i])) t--;

             q[++t]=rk[i];

         } else {

             while (h<t&&cmp2(q[h],q[h+],a[rk[i]])) h++;

             f[rk[i]]=min(f[rk[i]],f[q[h]]+1LL*(a[rk[i]]-a[q[h]])*(a[rk[i]]-a[q[h]]));

         }

     }

     solve(mid+,r);

  }

 int main(){

     init();

     if (n<=) force();

     if (flag) solve(,n);

     printf("%.4f",sqrt(f[n]));

 }