经验总结

  1. 首页 > 生活 > >

dp优化 | 各种dp优化方式例题精选( 三 )

生活百科

3. 斜率优化dpOI-Wiki 传送门
3.1 P3195 [HNOI2008]玩具装箱3.1.1 题目大意有 \(n\) 件物品 ， 第 \(i\) 件物品压缩后占用 \(C_i\) 的长度 。
现需把这些物品压缩进一些容器里 ， 制作一个容器的花费为 \((x-L)^2\) ， 其中 \(x\) 表示容器长度 。
每个容器中的物品编号需要是连续的 ， 而将编号 \(i\) 到 \(j\) 的所有物品放在一个容器中 ， 占用的空间 \(x=j-i+\sum_{k=i}^j C_k\) 。
求压缩完所有物品所需的总花费的最小值 。
3.1.2 数据范围\(1\leq n\leq 5\times10^4\) ， \(1\leq L\leq10^7\) ， \(1\leq C_i\leq10^7\) 。
3.1.3 做法设 \(f_i\) 表示压缩到第 \(i\) 件物品所需的最小花费 ， 不难列出转移方程：
\(f_i=\min\{f_j+(i-j-1+\sum_{k=j+1}^i c_k-L)^2\}\)
令 \(sum_i=\sum_{k=1}^i c_k\) ， 原式可转化为：
\(f_i=\min\{f_j+(i-j-1+sum_i-sum_j-L)^2\}\) 。
移项得：
\(f_i=\min\{f_j+((i+sum_i)-(j+sum_j)-(L+1))^2\}\)
令 \(pre_i=sum_i+i\) ， 原式可转化为：
\(f_i=\min\{f_j+(pre_i-pre_j-(L+1))^2\}\)
把式子展开再合并：
\(f_i=\min\{f_j+pre_i^2-pre_i\times pre_j-(L+1)\times pre_i-pre_i\times pre_j+pre_j^2+(L+1)\times pre_j-(L+1)\times pre_i+(L+1)\times pre_j+(L+1)^2\}\)
\(f_i=\min\{f_j+pre_i^2+pre_j^2-2\times pre_i\times pre_j-2\times(L+1)\times(pre_i-pre_j)+(L+1)^2\}\)
\(f_i=\min\{f_j+(pre_i-pre_j)^2-2\times(pre_i-pre_j)\times(L+1)+(L+1)^2\}\)
\(f_i=\min\{f_j+(pre_i-pre_j-(L+1))^2\}\)
\(f_i=\min\{f_j+((pre_i-(L+1))-pre_j)^2\}\)
\(f_i=\min\{f_j+(pre_i-(L+1))^2-2\times(pre_i-(L+1))\times pre_j+pre_j^2\}\)
\(f_i-(pre_i-(L+1))^2=\min\{f_j+pre_j^2-2\times(pre_i-(L+1))\times pre_j\}\)
令:
\(\begin{eqnarray}\begin{cases}b_i=f_i-(pre_i-(L+1)^2)\\x_j=pre_j\\y_j=f_j+pre_j^2\\k_i=2\times(pre_i-(L+1))\end{cases}\end{eqnarray}\)
发现原式转化为 \(b_i=\min\{y_j-k_i\times x_j\}\) 。
看上去有那么亿点点的像 \(y=kx+b\) 呢……
考虑这个求 \(b_i\) 的最小值的过程 ， 就是在最小化直线的截距 。把 \((x_j,y_j)\) 看作平面上的一个点 ， 现在有一条斜率为 \(k_i\) 的直线 ， 从下往上找（最小化） ， 找到的第一个点就是转移决策点 。
实际上 ， 只需维护下凸壳的那些点 。
对于本题 ， \(k_i\) 随 \(i\) 的增大而增大 ， 所以可以用单调队列进行维护 。
const int N = 50010;int n, c[N], l = 1, r = 0;;ll sum[N], s[N], f[N], L;ll Get(int x) { return f[x] + (sum[x] + L) * (sum[x] + L);}long double slope(int x, int y) { return (Get(y) - Get(x)) * 1.0 / (sum[y] - sum[x]);}int main() { n = read(), L = read() + 1; for (int i = 1; i <= n; i++) c[i] = read(); for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + c[i] + 1; s[++r] = 0; for (int i = 1; i <= n; i++) {while (l < r && slope(s[l], s[l + 1]) <= (sum[i] << 1)) l++;f[i] = f[s[l]] + (sum[i] - sum[s[l]] - L) * (sum[i] - sum[s[l]] - L);while (l <= r && slope(s[r - 1], s[r]) >= slope(s[r - 1], i)) r--;s[++r] = i;}printf("%lld\n", f[n]); return 0;}N. 参考内容DP优化 - zuytong
单调队列优化DP - superPG
【dp优化 | 各种dp优化方式例题精选】

经验总结扩展阅读


上一篇：故事 --- Linux和UNIX之间的那些爱恨与情仇

下一篇：男孩变声后的生长规律