P4655 [CEOI2017] Building Bridges

题意：　有 n 根柱子，第 i 根的高度是 a[i]，你可以选择保留一些，其他的全被拆掉。

　　　　拆除第 i 根柱子的代价是 w[i]，保留的柱子中相邻的两条柱子的代价是它们高度差的平方。

　　　　第一根和最后一根是必须保留的。

思路：假设选择连接 i 和 j，那么对于区间 [i,j] 的代价为 (a[i]-a[j])*(a[i]-a[j])+w[k] i<k<j

　　　所以 f[j]=min(f[j],f[i]+(a[i]-a[j])*(a[i]-a[j])+sum[j-1]-sum[i])

　　这是 O(n²) 的做法。

将 f[j] 展开，得：f[j]=f[i]+a[i]*a[i]+a[j]*a[j]+sum[j-1]-sum[i]-2*a[i]*a[j]

　　移项，得：f[j]-sum[j-1]-a[j]*a[j]=f[i]+a[i]*a[i]-2*a[i]*a[j]

我们发现，sum[j-1] 和 a[j]*a[j] 不会影响答案，答案取决于 f[i]+a[i]*a[i]-2*a[i]*a[j]

这个式子有两个变量，f[i]+a[i]*a[i] 是已知的，令其等于 h[i]

对于 i<k，如果 h[i]-2*a[i]*a[j]<=h[k]-2*a[k]*a[j]

　　　　那么 h[i]-h[k]<=2*a[j]*(a[i]-a[k])

　　　　所以 h[i]-h[k]/(a[i]-a[k])<=2*a[j]

我们以 (a[i],h[i]),(a[k],h[k]) 作为坐标轴上的点，如果两点间斜率小于 2*a[j]，那么 i 是更优解，否则 k 是更优解

到现在，如果我们需要处理每一对点对，时间复杂度仍然是 O(n^₂) ，我们试着模拟一下插入的过程。

一开始，只有一个点

斜率优化