题意:给定一个序列${C_i}$,将这个序列分段,其中每段装入一个容器,$[i,j]$这段的容器的长度为$\sum_{k=j}^{i} C_k +i-j-1$,问序列中所有数全部分段装容器以后的最小花费。
容易得到最朴素的式子$dp[i]=min_{j=0}^{i-1} (dp[j]+(i-j-1+\sum_{k=j+1}^{i} {C_k}-L)^2)$
记录前缀和为$sum[i]$可以得到$dp[i]=min_{j=0}^{i-1} (dp[j]+(i-j-1+sum[i]-sum[j]-L)^2)$
直接算复杂度为$O(n^2)$,考虑斜率优化
上式为$dp[i]=min_{j=0}^{i-1} (dp[j]+(i+sum[i]-j-sum[j]-L-1)^2)$
令$f(i)=sum[i]+i$,则$dp[i]=min_{j=0}^{i-1} (dp[j]+(f(i)-f(j)-L-1)^2)$
假定对于$dp[i]$,有决策点$j,k(j<k)$,如果$k$比$j$更优,
那么$dp[j]+(f(i)-f(j)-L-1)^2)>dp[k]+(f(i)-f(k)-L-1)^2$
拆平方,移项得$dp[j]+f^2(j)-(dp[k]+f^2(k))+2(f(j)-f(k))\cdot(L+1)>2f(i)\cdot (f(j)-f(k))$
$\frac{dp[j]+f^2(j)-(dp[k]+f^2(k))}{f(j)-f(k)}<2(f(i)-L-1)$
$\frac{dp[j]+f^2(j)-(dp[k]+f^2(k))+2(L+1)(f(j)-f(k))}{f(j)-f(k)}<2f(i)$
$\frac{dp[j]+(f(j)+L+1)^2-dp(k)-(f(k)+L+1)^2}{2(f(j)-f(k))}<f(i)$
令$g(j,k)=\frac{dp[j]+(f(j)+L+1)^2-dp(k)-(f(k)+L+1)^2}{2(f(j)-f(k))}$,则当$g(j,k)<f(i)$时,$k$比$j$更优。
同时考虑一个情形,当$g(l,j)>g(j,k)$的时候,$j$一定不是最优决策点,简证:
- 当$g(l,j)>f(i)$($i$为当前要更新的下标),j不是最优;
- 当$g(l,j)\leq f(i)$,由于$g(l,j)>g(j,k)$,故$g(j,k)<f(i)$,$j$没有$k$优,$j$也不是最优决策点
得证,这个性质用于弹出队尾。
维护一个队列,当中存所有最优的决策点(对于当前$i$而言),$l$为队首,$r$为队尾,
当$g(q[l],q[l+1])<f(i)$时,弹掉队首;
当$g(q[r-1],q[r])<g(q[r],i)$时,弹掉队尾。
这样可以每次$O(1)$更新答案,总复杂度为$O(n)$
|
|