杭州做网站公司有哪些,青岛网站制作公司 网络服务,佛山网站建设找方维网络,桥头做网站感觉贪心的做法比较自然#x1f914;#xff0c;推荐 这篇博客
非常经典牛逼的贪心思路#xff1a;
考虑每次加入一个数#xff0c;位置 i i i的贡献为 V i k i a i b i V_ik_i\times a_ib_i Vikiaibi#xff0c;其中 k i k_i ki表示 i i i以前被选的位置的…感觉贪心的做法比较自然推荐 这篇博客
非常经典牛逼的贪心思路
考虑每次加入一个数位置 i i i的贡献为 V i k i × a i b i V_ik_i\times a_ib_i Viki×aibi其中 k i k_i ki表示 i i i以前被选的位置的个数 b i b_i bi表示 i i i以后被选的数的和
发现每次都会加入当前贡献最大的数。想一想会发现非常对可以用归纳调整法证明。感觉就是拟阵啊
这样我们考虑分块发现对于整块的询问本质上就是维护凸包类似于斜率优化这样就做完了
事实上我们不需要在凸包上二分注意到询问的 k k k是递增的因此不断弹出队头元素即可
复杂度 O ( n n ) O(n\sqrt{n}) O(nn )。 remark \text{remark} remark 别把凸优化学魔怔了。。。不是啥题都要用 D P DP DP。。。
