10188. 「一本通 5.6 练习 1」玩具装箱

Link

题意

你可以将一段连续的玩具扔到同一个容器中,如果要将 $i$ 号玩具到 $j$ 号玩具 $(i\le j)$ 放到同一个容器中,则容器长度不小于 $x=j-i+ \displaystyle\sum_{k=i}^{j}C_k$制作容器的费用与容器的长度有关,根据教授研究,如果容器长度为 $x$,其制作费用为 $(X-L)^2$,其中 $L$ 是一个常量。
求最小花费。
对于全部数据,$1\le N\le 5\times 10^4,1\le L,C_i\le 10^7$。

思路

首先,考虑$dp$。
设$f[i]$表示前$i$个玩具的最小花费,那么最终的答案就是$f[n]$。
那么很容易就可以得知:$f[i]=min(f[j]+(i-j+\sum_{k=i}^{j}C_k-L-1)^2)(1\leq j <i,1\leq i\leq n)$
考虑优化。

优化1

设$sum[i]$表示$C$数组的前缀和,那么转移方程可化为:$f[i]=min(f[j]+(i-j-sum[j]+sum[i]-L-1)^2)(1<=i<=n,1<=j<i)$
时间复杂度:$O(N^3)–>O(N^2)$
预计得分:20pt

优化2

考虑斜率优化。
原转移方程可化为:$f[i]=f[j]+(i+sum[i]-L-1-sum[j]-j)^2$
设$A[i]=sum[i]+i$,$B[i]=sum[i]+i-L-1$
则$f[i]=f[j]+(A[i]-B[j])^2$,
$f[i]=f[j]+A[i]^2+B[j]^2-2\times A[i]\times B[j]$,
$2\times A[i]\times B[j]+f[i]-A[i]^2=f[j]+B[j]^2$。
设$x=B[j],y=f[j]+B[j]^2$,
那么$y=x\times (2\times A[i])+(f[i]-A[i]^2),slope=2\times A[i]$。
$f[i]=y+A[i]^2-2\times A[i]\times x$。
那么就斜率优化鸭。

Code

暂无评论

发送评论


				
上一篇
下一篇