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\)然后得不到最优解了。
定理:每次选择\(Q_i\)最大的总能得到最优解。
\(proof:\)
假设最后最优解的大小为\(S\)。
和引理的证明类似:通过假设反证,设当前为第一个无法到达最优解的时刻。
设在加入当前的\(a_i\)之前的集合为\(A\),根据它可以构造出的最优解集合为\(B\),则\(A\sub B\)。
令\(B‘=\complement_BA\)。
可以发现\(B‘\neq \empty\),\(a_i\not\in B‘\)。
分两种情况:
这样我们只需要维护\(Q_i\),然后全局查询最小值就可以了。
可以发现我们对于\(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)\)
对上述的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: 徐翊轩的题解
原文:https://www.cnblogs.com/gary-2005/p/14274260.html