#P8655. 打怪兽

    ID: 8742 传统题 4000ms 512MiB 尝试: 3 已通过: 2 难度: 7 上传者: 标签>动态规划贪心CF2300单调队列优化二分前缀和排序

打怪兽

叠甲

本地 Hydro 评测时限:4 秒。内存限制:512 MB。

题目描述

Dr 正在打怪兽,初始护甲为 00。怪兽在第 ii 回合攻击,若当时护甲为 kk,造成的伤害为 max⁡(ai−k,0)\max(a_i-k,0)。每回合结束后,若护甲大于 00,则减少 11 点。

Dr 可以在任意时刻增加任意多点护甲。对每个 D=1,…,nD=1,\ldots,n,求总共增加 DD 点护甲时,全部 nn 回合伤害总和的最小值。

输入格式

第一行一个整数 nn。第二行 nn 个整数 aia_i,表示每回合的攻击值。每个攻击值按完整十进制整数读取,不依赖额外的数值上界。

输出格式

输出 nn 行,第 DD 行表示总共增加 DD 点护甲时的最小伤害总和。

数据范围

  • 20%20\%:n≤10n\le10。
  • 50%50\%:n≤500n\le500。
  • 全部数据:1≤n≤40001\le n\le4000。

攻击值大于 nn 时,可先减去固定伤害 ai−na_i-n,再用 nn 代替该攻击值;总增加护甲数最多为 nn,这个等价变换不改变任何方案的相对优劣。答案可能超过64位,应按完整十进制整数输出。