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)
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <algorithm> 5 using namespace std; 6 7 #define maxn 100008 8 #define LL long long 9 10 long long f[maxn]; 11 int a[maxn],b[maxn]; 12 int n; 13 bool flag=1; 14 15 void read(int &x){ 16 char ch; 17 for (ch=getchar();ch<'0'||ch>'9';ch=getchar()); x=ch-48; 18 for (ch=getchar();ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-48; 19 } 20 21 void init(){ 22 read(n); 23 for (int i=1;i<=n;i++) { read(a[i]); read(b[i]); if (b[i]) flag=0; } 24 for (int i=1;i<=n;i++) f[i]=(LL)1<<60; 25 } 26 27 void force(){ 28 for (int i=1;i<=n;i++) 29 for (int j=0;j<=i-1;j++) 30 if (a[j]>=b[i]) 31 f[i]=min(f[i],f[j]+(LL)(a[i]-a[j])*(a[i]-a[j])); 32 33 } 34 35 int q[maxn],rk[maxn]; 36 bool cmp(int i,int j){ 37 return a[i]<a[j] ; 38 } 39 40 long long kx(int i,int j){ 41 return 2*(a[i]-a[j]); 42 } 43 44 long long ky(int i,int j){ 45 long long ans=1LL*a[i]*a[i]+f[i]-1LL*a[j]*a[j]-f[j]; 46 return ans; 47 } 48 49 bool cmp1(int i,int j,int k){ 50 return ky(k,j)*kx(j,i)<=kx(k,j)*ky(j,i); 51 } 52 53 bool cmp2(int i,int j,int k){ 54 return ky(i,j)>=k*kx(i,j); 55 } 56 57 void solve(int l,int r){ 58 if (l==r) return; 59 int mid=(l+r)>>1; 60 solve(l,mid); 61 for (int i=l;i<=r;i++) rk[i]=i; 62 sort(rk+l,rk+r+1,cmp); 63 int h=1,t=0; 64 for (int i=l;i<=r;i++) 65 { 66 if (rk[i]<=mid) { 67 while (h<t&&cmp1(q[t-1],q[t],rk[i])) t--; 68 q[++t]=rk[i]; 69 } else { 70 while (h<t&&cmp2(q[h],q[h+1],a[rk[i]])) h++; 71 f[rk[i]]=min(f[rk[i]],f[q[h]]+1LL*(a[rk[i]]-a[q[h]])*(a[rk[i]]-a[q[h]])); 72 } 73 } 74 solve(mid+1,r); 75 } 76 int main(){ 77 init(); 78 if (n<=1000) force(); 79 if (flag) solve(0,n); 80 printf("%.4f",sqrt(f[n])); 81 }