配点 : 700 点
問題文
你别无选择,只能 1 纸张和长度 N 整数序列 我想到了使用 A_1, A_2, \ldots, A_N 的以下游戏。
首先,在一张纸上写下您最喜欢的正整数。 1 我会写一篇。之后 执行 N 操作。 对于 i 回目 (1\le i\le N) 操作,可以: 1 做一件事。
- 当时纸上写的数字 作为 X ,Y = \left \lfloor\frac{A_i}{X}\right \rfloor ( 表示\lfloor x \rfloor 考虑一块分为 x )的整数部分。写在纸上的数字 将其重写为 Y ,Y 赚取积分。 注意这个操作 当 X > A_i 时,无法执行此操作。
- 什么都不做。连积分都拿不到。
你别无选择,只能 N 我想最大化一次操作中获得的积分总数。
你写在纸上的第一个数字 N 找出通过最佳执行操作可以获得的积分。
制約
- 1\le N\le 1000
- 1\le A_i\le 10^6
- 输入都是整数
部分点
这个问题有部分要点。 关于
- 全部 关于 i\ (1\le i\le N) 如果您正确回答满足 A_i\le 1000 的输入, 将获得300 积分。
入力
输入是按以下格式从标准输入给出的。
N A_1\ A_2\ \ldots\ A_N
出力
我们别无选择,只能设置您可以获得的最大积分数。 在 1 行输出。
入力例 1
3 3 6 9
出力例 1
10
- 首先在纸上 写入 2 。
- 1 对于第二个操作,更改纸上的数字。 将其重写为 \left \lfloor\frac{3}{2}\right \rfloor = 1 将其重写为 1 赚取积分。
- 2 第二个操作不执行任何操作。
- 3 对于第二个操作,更改纸上的数字。 将其重写为 \left \lfloor\frac{9}{1}\right \rfloor = 9 将其重写为 9 赚取积分。
此时总计 10 你可以获得积分,这是最高的。此外,10 还有其他赚取积分的方法。
入力例 2
3 10 3 4
出力例 2
10
入力例 3
1 1000
出力例 3
1000
入力例 4
10 87 72 55 81 12 59 1 10 18 53
出力例 4
166