【题解】玩具装箱toy BZOJ1010 斜率优化DP

萌萌哒传送门
自己做的斜率优化第一题,然而中途有点不记得了又翻了HDU3507的代码。。。还看了下别人的代码看会不会爆long long(其实对于不会爆long long这个问题我自己的证明好像不够严密,说白了就是乱想了一下,这种不严谨的东西就不写出来了)
然后,我没有想出二维DP方程来(雾),于是上网借鉴了一下。。。
(好吧这根本就不是自己做的了)
我怎么这么菜啊。。。

终于可以进入正题了。
我们可以得到二维的状态转移方程。
\(dp[i]=min\{dp[j]+(sum[i]-sum[j]+i-j-1-L)^2,dp[i]\}\ (0\le j\lt i)\)
然后开始优化。

1.证明决策的单调性

说直接一点,就是要证明,决策到i时,假设\(k\lt j\lt i\),如果从j转移比从k转移更优,那么决策到t时(\(t\gt i\)),从j转移同样比从k转移更优。
决策到i时,我们有
\(dp[j]+(sum[i]-sum[j]+i-j-1-L)^2\lt dp[k]+(sum[i]-sum[k]+i-k-1-L)^2\)
设\(f[i]=sum[i]+i\)
那么就有
\(dp[j]+(f[i]-f[j]-1-L)^2\lt dp[k]+(f[i]-f[k]-1-L)^2\)
现在我们要证明,决策到t时
\(dp[j]+(f[t]-f[j]-1-L)^2\lt dp[k]+(f[t]-f[k]-1-L)^2\)
再假设\(f[t]=f[i]+v\)
那么就要证明
\(dp[j]+(f[i]+v-f[j]-1-L)^2\lt dp[k]+(f[i]+v-f[k]-1-L)^2\)
也就是说要证明
\(dp[j]+(f[i]-f[j]-1-L)^2+v^2+2\times v\times (f[i]-f[j]-1-L)\lt dp[k]+(f[i]-f[k]-1-L)^2+v^2+2\times v\times (f[i]-f[k]-1-L)\)
由于之前证明过\(dp[j]+(f[i]-f[j]-1-L)^2\lt dp[k]+(f[i]-f[k]-1-L)^2\)
那么现在只需证明
\(2\times v\times (f[i]-f[j]-1-L)\lt 2\times v\times (f[i]-f[k]-1-L)\)

\(f[j]\gt f[k]\)
根据之前对\(f[i]\)的定义,这显然是成立的。
证明完毕。

2.求斜率方程

根据上一部分,我们已经知道
\(dp[j]+(f[i]-f[j]-1-L)^2\lt dp[k]+(f[i]-f[k]-1-L)^2\ (k\lt j\lt i)\)
设\(a[i]=sum[i]+i-1-L\),对上式展开再移项,可以得到
\((dp[j]+f[j]^2)-(dp[k]+f[k]^2)\lt 2\times a[i]\times (f[j]-f[k])\)
由于\(f[j]\gt f[k]\),我们可以再把\(a[i]\)单独留在右边
\(\frac{(dp[j]+f[j]^2)-(dp[k]+f[k]^2)}{2\times (f[j]-f[k])}\lt a[i]\)
下面的过程和HDU3507几乎一样,由于\(f[i]\)递增,用单调队列来维护这个凸包即可。