【学习笔记】CF573E Bear and Bowling

感觉贪心的做法比较自然?，推荐这篇博客

非常经典牛逼的贪心思路：

考虑每次加入一个数，位置 $i$ 的贡献为 $V_i=k_i\times a_i+b_i$ ，其中 $k_i$ 表示 $i$ 以前被选的位置的个数， $b_i$ 表示 $i$ 以后被选的数的和

发现每次都会加入当前贡献最大的数。想一想会发现非常对，可以用归纳+调整法证明。感觉就是拟阵啊？

这样，我们考虑分块，发现对于整块的询问本质上就是维护凸包（类似于斜率优化），这样就做完了

事实上我们不需要在凸包上二分，注意到询问的 $k$ 是递增的，因此不断弹出队头元素即可

复杂度 $O(n\sqrt{n})$ 。

$\text{remark}$ 别把凸优化学魔怔了。。。不是啥题都要用 $D P$ 。。。文章来源地址https://uudwc.com/A/9dpgL

原文地址:https://blog.csdn.net/cqbzlydd/article/details/133103502

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：如若内容造成侵权/违法违规/事实不符，请联系站长进行投诉反馈，一经查实，立即删除！