P3195 [HNOI2008]玩具装箱
容易推出式子 \(dp[i]=min(dp[i],dp[j]+(i-j-1+s[i]-s[j]-L)^2)\)
故设 \(A[i]=i+s[i]-L-1\) (与 \(j\) 无关的项)
\(B[i]=i+s[i]\)
故如果 \(dp[j]+(i-j-1+s[i]-s[j]-L)^2)\) 就是答案，则 \(dp[i]=dp[j]+(A[i]-B[j])^2\)
分解得 \(dp[i]=dp[j]+A[i]^2+B[j]^2-2A[i]B[j]\)
而斜率优化就是用来解决 \(dp[i]=a[i]\times b[j]+c[i]+d[j]\) 的。
我们将式子变成 \(b[j]^2+dp[j]=2A[i]B[j]-A[i]^2+dp[i]\)
其中 \(2A[i],-A[i]^2+dp[i]\) 为常数，故得出函数 \(y=kx+b\)
\(y\) 表示 \(b[j]^2+dp[j]\)，\(x\) 表示 \(b[j]\)
\(k,b\) 可简单得知。
其中的 \(x\) 都是孤立的点，\(dp[i]=b-A[i]^2\)，所以 \(b\) （截距）越小，\(dp[i]\) 越小。
通过数形结合可得出斜率第一个大于等于 \(k\) 的点，可保证 \(b\) 最小。
为何？因为这条斜率为 \(2A[i]\) 的直线不能插进凸包。
于是便找到了最优解。
再维护个凸包就行。