AT_cpsco2019_s1_g.Game with Division

やむなく君设计了一个使用 $1$ 张纸和一个长度为 $N$ 的整数序列 $A_1,\ A_2,\ \ldots,\ A_N$ 的游戏，规则如下：

首先，你可以在纸上写下任意一个正整数。之后，你需要进行 $N$ 次操作。第 $i$ 次操作（$1\leq i\leq N$）时，你可以选择以下两种操作之一：

• 设此时纸上写的数字为 $X$，则令 $Y = \left\lfloor \frac{A_i}{X} \right\rfloor$（$\lfloor x \rfloor$ 表示 $x$ 的整数部分）。将纸上的数字改写为 $Y$，并获得 $Y$ 分。如果 $X > A_i$，则不能进行此操作。
• 什么都不做，也不会获得分数。

やむなく君想通过最优地选择最初写在纸上的数字以及每一步的操作方式，使得 $N$ 次操作获得的总分最大。

请你求出やむなく君能够获得的最大总分。

输入以如下格式从标准输入读入：

$N$
$A_1\ A_2\ \ldots\ A_N$

请输出やむなく君能够获得的最大总分。

限制条件

• $1\leq N\leq 1000$
• $1\leq A_i\leq 10^6$
• 所有输入均为整数

部分得分

本题设置了部分得分。

• 如果你能正确解决所有满足 $A_i\leq 1000$ 的输入，将获得 $300$ 分。

样例解释 1

• 首先在纸上写下 $2$。
• 第 $1$ 次操作时，将纸上的数字改写为 $\left\lfloor \frac{3}{2} \right\rfloor = 1$，获得 $1$ 分。
• 第 $2$ 次操作时什么都不做。
• 第 $3$ 次操作时，将纸上的数字改写为 $\left\lfloor \frac{9}{1} \right\rfloor = 9$，获得 $9$ 分。

此时总共获得 $10$ 分，这是最大值。实际上，获得 $10$ 分的方法不止一种。

由 ChatGPT 4.1 翻译