这种题目首先我们可以想一个比较蠢的 \(n^2\) DP，然后观察一些性质来优化它。
那很显然我们可以设 \(f_{i,j}\) 表示前 \(j\) 个数选了 \(i\) 个，有
\[f_{i,j}=\max(f_{i,j-1},f_{i-1,j-1}+a_j\cdot i)
\]
写个暴力，先猜了一手凸性发现错了，又猜了一手决策单调发现对了。
具体来说，对于第 \(j\) 个数而言，我们可以找到一个分界点 \(p\)，使得 \(i\le p\) 时它不被选，\(i>p\) 时它被选。
接下来我们想怎么用这个性质去优化。分界点可以直接二分一手找到，左侧保留，右侧加一个等差数列。
我们可以先开好所有的位置，然后用平衡树维护，复杂度 \(O(n\log^2n)\)，实现好一点应该可以做到 1 log。