先考虑朴素动规，设 \(f_{i,j,m}\) 表示前 \(i\) 个人，目前的最大值是 \(m\)，用了 \(j\) 张牌，最终对答案的贡献是什么。那么有转移：
\[f_{i,j,m}=\max(f_{i-1,j,m},\max_{v=1}^{m-1}(f_{i-1,j-m,v}+(m-v)(n-i+1))
\]
那么不妨设 \(w=n-i+1\)，则公式转为：
\[f_{i,j,m}=\max(f_{i-1,j,m},mw+\max_{v=1}^{m-1}(f_{i-1,j-m,v}-vw))
\]
可以使用前缀和优化里面那个式子做到 \(O(nk^2)\)。但我们发现，如果存在一个 \(i<j\land a_i\geq a_j\)，我们 不可能在 \(j\) 上浪费任何牌。否则若 \(a_i\) 没有填满，我们在 \(a_i\) 上填一定对后面更优，如果填满了那么我们就不用填了因为再怎么填最大值不变。那么因为 \(a^\prime\) 单调递增，所以之多只有 \(k\) 个元素，我们就可以优化到 \(O(n+k^3)\) 了。