【BZOJ1010】【HNOI2008】玩具装箱

AC数rank 3

感觉这题就是个**dp 想着赶快切了这道题的

\(dp_i\)表示以i为结尾的答案那么

$$dp_i=min(dp_j+(i-j-1-L+\sum_{k\in(j,i]}c_k)^2)(j< i)$$

然而发现复杂度好像不对?

然后只好找hzwer发现要斜率优化

然而我还不会【去学啦】

好吧 推了半节晚自习终于搞清楚这玩意是干啥的了

首先,第一步要证明这个dp满足决策单调性,

即对于某个点i,若j处决策优于k处决策且k<j,那么对于所有p>i,在j处的决策也一定优于k处决策。

对于这道题而言,手推推就能发现他满足决策单调性。

然后,要找到他的斜率方程。

即找出一个这样子的式子,当该式成立时在对于i而言决策j优于决策k(k<j)。

一般形式是:

$$f1(i)>\frac{f2(j)-f2(k)}{f3(j)-f3(k)}$$

其中f1、f3为单调函数

这样我们可以把每个\((f3(i),f2(i))\)映射到平面上的一个点

那么若两个点之间的斜率小于f1(i)说明对于i来说出发点决策劣于到达点决策。那么就可以从平面上剔除这个点。

我们同时可以证明我们要维护的是一个下凸壳:如果存在三个点i,j,k满足i<j<k且k(i,j)>k(j,k),那么当i劣于j时f1(i)>k(i,j)>k(j,k),说明j劣于k,j永远不会被取到。

既然是下凸壳,那么斜率一定递增。那么满足和下一个点斜率不小于f1的第一个点即为当前的最优决策点。

于是这道题就很容易啦。

说点什么

  Subscribe  
提醒