← 返回题目列表

AtCoder · m_solutions2020_d

D. 百万富翁之路

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

为了成为百万富翁,M君决定通过交易下一个来赚钱 N 天。目前,他已 1000 日元,没有股票 - 他居住的国家只发行一种股票。

他因预知未来的能力而闻名全国。他已经知道下一只股票的价格 N 天数如下:

  • A_1 日元上 1第一天, A_2 日元上 2- 第一天,..., A_N 日元上 N第一天。

在 i第天,M君可以进行以下交易 任意次数 (可能为零), 在他当时拥有的资金和股票数量之内.

  • 购买股票:支付 A_i 日元并收到一支股票。
  • 出售股票:出售一只股票 A_i 日元。

通过最优交易,M君最终能拥有的最大金额是多少?

约束

  • 2 \leq N \leq 80
  • 100 \leq A_i \leq 200
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \cdots A_N

输出

以整数形式打印出M-kun最终可以拥有的最大金额。


示例输入 1

7
100 130 130 130 115 115 150

示例输出 1

1685

在此示例输入中,M-kun 有 7 天的交易时间。一种方法是拥有 1685 日元最终如下:

  • 最初,他有 1000 日元,没有库存。
  • 天 1:购买 10 库存为 1000 日元。现在他有 0 日元。
  • 天 2:出售 7 库存为 910 日元。现在他有 910 日元。
  • 天 3:出售 3 库存为 390 日元。现在他有 1300 日元。
  • 天 4:什么都不做。
  • 天 5:购买 1 库存为 115 日元。现在他有 1185 日元。
  • 天 6:购买 10 库存为 1150 日元。现在他有 35 日元。
  • 天 7:出售 11 库存为 1650 日元。现在他有 1685 日元。

没有办法拥有 1686 日元或更多,所以答案是 1685.


示例输入 2

6
200 180 160 140 120 100

示例输出 2

1000

在此示例输入中,最好在六天内什么都不做,之后我们将得到 1000 日元。


示例输入 3

2
157 193

示例输出 3

1216

在此示例输入中,最佳购买 6 当日股票 1 并在日内出售它们 2,之后我们将有 1216 日元。