Loading...
简单的背包问题+结论证明引入考虑一个问题：一个集合中有 $n$ 个物品，每个物品有一个价值(可能为负)，请你取出 $m$ 个物品，并且使价值之和最大。这种问题一般人选择直接排序，但是如果一个物品的价值计算方式变化了导致不能直接排序取出，甚至没有贪心策略时，应该如何做？如果直接使用二维dp还会超时有什么办法可以快速做？推结论实际上这个问题就是WQS问题的典型问题，我们设函数 $\operato...
前言本文宗旨解释一下斜率优化本质问题，而不是表面上的讲解一个模板，本文可以作为一个较为权威的资料参考学习，但不建议直接使用本材料第一次学习斜率优化，这样只...
P3195 [HNOI2008]玩具装箱模板题。斜率递增，X递增，min/维护上凸壳，单调队列即可。P5017 [NOIP2018 普及组] 摆渡车推式子有一定难度。上凸壳，单调队列即可。P2365 任务安排推式子有一定技巧性。仍然是上凸壳，单调队列即可。P2365 特别行动队打好基础，同上。P2120 [ZJOI2007] 仓库建设打好基础，同上。P5785 [SDOI2012]任务安排上...
本文同时可以在洛谷“Zi_Gao的博客”上查看，后续更新在此不会贴出来。$\sum\limits_{s_1={p_1}}^{q_1}\sum\limits...
本文同时可以在洛谷“Zi_Gao的博客”上查看，后续更新在此不会贴出来。P4247 [清华集训2012]序列操作 题解首先这道题从各个方面都知道是线段树。0x00 记号与约定所有的运算符号如 $+$ 、 $=+$ 、 $==$ 等，与c++意义相同。 $\oplus$ 表示异或运算。所有的下表从1开始。$tree_{p}$ 表示第 $p$ 个线段树节点。$tree_{p}.l$ 表示第 $p...