题解

题面描述

有一个 $n$ 层的珠宝塔，每一层都有无限数量的一种珠宝。第 $i$ 层的珠宝需要花费 $i$ 个金币购买，而每个珠宝的价值为 $a_i$ 。每当你第一次进入第 $i$ 层时，会获得 $k_i$ 个金币作为奖励。
从第 $1$ 层开始向上，每层到达后你都有两种选择：

ALLIN：花光当前所有金币购买该层珠宝。由于没有找零机制，即使你手中的金币数不能被 $i$ 整除，也只能购买 $\lfloor \frac{x}{i} \rfloor$ 个珠宝，从而获得价值 $\lfloor \frac{x}{i} \rfloor \times a_i$ ，此时金币清零，然后进入第 $i+1$ 层。
SKIP：不进行购买，直接进入第 $i+1$ 层（若在第 $n$ 层则直接离开）。

1000ms

Difficulty: 6

所属公司 : 蚂蚁

算法与标签>动态规划

有一个 $n$ 层的珠宝塔，每一层都有一种珠宝数量无限。具体地，第 $i$ 层的珠宝价格为 $i$ 个金币价值为 $a_i$ 。

现在，您将从第 $1$ 层开始，逐层向上攀登。每当你第一次进入第 $i$ 层时，你将会得到 $k_i$ 个金币的初始奖励，而后你有两种选择：

$ALLIN$ ：花光所有金币，购买当前层的珠宝，并且，由于不设找零，所以多花的钱会直接消失(即假如你有 $x$ 个金币，你将得到 $\frac{x}{i}×a_i$ 的价值，并且你手中金币数将变为 $0$ )；随后进入第 $i+1$ 层；
$SKIP$ ：直接进入第 $i+1$ 层，如果此时你位于第 $n$ 层你将会直接离开珠宝塔。

编辑器加载中…

输入

预期输出（选填）