夏晓光(loveJY)的博客

每日推荐

建议标签:凸包+栈

首先我们可以考虑怎么二分,因为如果一个时间点之前的可以那么之后的也一定可以

然后你会发现好像不太会写check函数,因为如果使用$O(n^2)$DP的话就不需要二分了.....

有一个显然的性质是我们只会使用当前最优的工厂,而且我们达到S之前一定有一段连续使用一个工厂...

然后我冥思苦想了一下,突然脑袋里浮现出斜率优化时的凸包

如果我们把time当做x轴,value当做y轴的话,我们就可以把每个工厂看成一个直线了,不用管截距,至少他的斜率很显然是$V_i$

那么截距其实就是达到$C_i$时的最优金币数X可以算出的!

哎?如果我们知道了截距,每个工厂的射线是不是就能围成一个每秒最优金币数的凸包了啊?

所以我们就是要对这些个直线进行处理,我们先把工厂按照代价排序,这样我们一定先可解锁之前的再解锁之后的

问题就变成我们对于之前的某个凸包状态可以计算出下一条新直线然后update新凸包的状态

做法也就很显然了:维护一个单调栈,栈中记录一条射线的起点坐标和斜率

然后枚举下个工厂,计算与凸包的交点,就是用单调栈计算出对于那个代价第一次达到的时间点以及最优金币数X,得到就可得到下一条射线

用这条射线加入单调栈,就是找他和凸包的交点,然后弹出不再是凸包的直线,可以证明在排序后一定是从栈顶连续的一些被弹出,而且之前计算的过程也一定是从栈底单调递增的一些射线和他求交,所以维护凸包的过程复杂度O(n)

最后复杂度在于排序的$O(nlogn)$

思路有些凌乱繁琐,但是做法还是很好懂的吧

未完code待续