1. CF573E Bear and Bowling
https://www.luogu.com.cn/problem/CF573E。
data structures, greedy。
题意：给定序列 \(a\)，求一个 \(a\) 的子序列 \(b\) 使得 \(\sum_{i=1}^k ib_i\) 最大。
\(n\leq 10^5\)。
本题满足决策包容性，即：
- 可以贪心地选择使答案最大的数加入子序列中。
- 设 dp，\(f_{i,j}\) 表示前 \(i\) 个数选 \(j\) 个，那么 \(f_{i-1}\to f_i\) 一定是一段前缀 \(j\) 不选，一段后缀选。且 \(\dfrac{f_i}i\) 单调递减。
这两个结论应该是等价的，且都可以继续优化。
第二个结论的优化方式是：找到第一个 \(\leq a_i\) 的 \(\dfrac{f_i}i\) 然后插入 \(a_i\)，平衡树维护。也可以直接分块。
https://codeforces.com/contest/573/submission/337949211。