首页 > 其他 > 详细

CF 573 E Bear and Bowling

时间:2021-01-13 21:05:09      阅读:25      评论:0      收藏:0      [点我收藏+]

CF 573 E Bear and Bowling

首先这题的主要思路是贪心。

\(Q_i\)表示当前时刻\(a_i\)加入集合对答案的贡献。

然后贪心的过程:每次选择\(Q_i\)最大的,直到选完,然后答案为每一步结束后的最大值。

证明

引理: 若\(i<j\and a_i>a_j\),则\(a_i\)一定在\(a_j\)之前被选择。

\(proof:\)

假设当前时刻,应该取\(a_j\),取了\(a_i\)然后得不到最优解了。

  • \(a_i\)\(a_j\)中间没有值,则将\(a_j\)换成\(a_i\)显然更优,与假设不符。
  • \(a_i\)\(a_j\)中间有值,则\(\forall k>i,a_k>a_i\)(根据引理)。考虑将他们分别从两种情况中删除:当前选择了\(a_i\)得到的集合,当前选择了\(a_j\)得到的集合。然后再一次加入,显然每一个\(a_k\)对于\(a_j\)的贡献为\(a_j\),对于\(a_i\)的贡献为\(a_k\)。由于\(a_k>a_i>a_j\),所以选择\(a_i\)更优。

定理:每次选择\(Q_i\)最大的总能得到最优解。

\(proof:\)

假设最后最优解的大小为\(S\)

和引理的证明类似:通过假设反证,设当前为第一个无法到达最优解的时刻。

设在加入当前的\(a_i\)之前的集合为\(A\),根据它可以构造出的最优解集合为\(B\),则\(A\sub B\)

\(B‘=\complement_BA\)

可以发现\(B‘\neq \empty\)\(a_i\not\in B‘\)

分两种情况:

  • \(B‘\)中所有的元素都在\(i\)的右侧:则考虑用\(a_i\)替换\(B‘\)中最左边,答案不会变得更劣
  • \(\exist k\in B‘,k<i\),取最大的\(k\),可以发现,根据引理,\(a_k<a_i\),答案不会变得更劣

这样我们只需要维护\(Q_i\),然后全局查询最小值就可以了。

实现方式:

1. 分块+维护凸包

可以发现我们对于\(Q_i\)的改动要不就是一段前缀+val,要不就是一段后缀Q[i]-=a[i]。

我们可以进行分块,然后每一块维护整体+的val,和-a[i]的数值,可以发现相当于有\(n\)个一次函数,形如:\(y=x*(-a[i])+b\)

\(b\)进行区间修改。

由于查询的\(x\)是递增的,所以可以不需要二分,实用two-pointers。

时间复杂度:\(O(N\times \sqrt N)\)

2. 平衡树+dp

对上述的greedy思想做一下总结可以发现,取\(x\)个得到的最优值是取\(x+1\)个得到的最优值的子集。

则设\(dp_{i,j}\)表示前i个取了\(j\)个的最优值,\(s_{i,j}\)为其方案。

则可以发现\(s_{i,j}\sub s_{i,j-1}\)

则选择加入\(a_i\)的是一段后缀。

可以用平衡树维护\(dp_{i,j}-dp_{i,j-1}\)。就可以了,每次二分找出修改开始的位置。

时间复杂度为\(O(N\log N)\)

Reference: 徐翊轩的题解

CF 573 E Bear and Bowling

原文:https://www.cnblogs.com/gary-2005/p/14274260.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!