Hexo
0%

dp优化整合

Posted on Edited on

斜率优化

P3195 [HNOI2008] 玩具装箱

考虑 dp，令 si=∑k=1icks_i=\sum^{i}_{k=1}c_k，dpidp_i 为 11 到 $ i$ 装箱的最小代价，则转移方程为 dpi=min⁡dpj+(i−j−1+si−sj−L)2(1≤j<i)dp_i=\min dp_j+(i-j-1+s_i-s_j-L)^2(1\le j<i)。

此时，为了方便，我们将所有的 sis_i 加 11，将 LL 也加 11，那么式子简化为 dpj+(si−sj−L)2=dpj+si2−2sisj−2siL+(sj+L)2dp_j+(s_i-s_j-L)^2=dp_j+s_i^2-2s_is_j-2s_iL+(s_j+L)^2。

此时，假设有 j0<j1j_0<j_1 且由 j1j_1 转移更优，则 dpj0+si2−2sisj0−2siL+(sj0+L)2≥dpj1+si2−2sisj1−2siL+(sj1+L)2dp_{j_0}+s_i^2-2s_is_{j_0}-2s_iL+(s_{j_0}+L)^2\ge dp_{j_1}+s_i^2-2s_is_{j_1}-2s_iL+(s_{j_1}+L)^2，即 (sj1−sj0)×2si≥[dpj1+(sj1+L)2]−[dpj0+(sj0+L)2](s_{j_1}-s_{j_0})\times 2s_i\ge [dp_{j_1}+(s_{j_1}+L)^2]-[dp_{j_0}+(s_{j_0}+L)^2]，由于显然 sj1≥sj0s_{j_1}\ge s_{j_0}，令 Yi=dpi+(si+L)2Y_i=dp_i+(s_i+L)^2，因此 2si≥Yj1−Yj0sj1−sj02s_i \ge \frac{Y_{j_1}-Y_{j_0}}{s_{j_1}-s_{j_0}}。