货架振幅之和 - problem_ide

登录查看题面

登录后即可查看完整题面内容。

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库，可解锁完整内容。

开通会员

题解：贡献法计数+前缀和

考虑第 $i$ 种货物对结果的贡献，选择第 $i$ 种货物对结果的贡献 $a_i \times (a_{i+1} \times 1 + a_{i+2} \times 2 + \dots + a_k \times (k-i))$

如果是选择第 $i+1$ 种货物，对结果的贡献为 $a_{i+1} \times (a_{i+2} \times 1 + a_{i+3} \times 2 + \dots + a_k \times (k-i-1))$

右边的差值其实就是 $a_{i+1} + a_{i+2} + \dots + a_k$

因此可以预处理一个后缀和数组来去一遍遍历，一遍计算，当然，也可以不使用后缀和数组，维护两个变量即可

编辑器加载中…

输入

预期输出（选填）