#P1064. 动态规划入门(一维一边推1:美元和马克)

动态规划入门(一维一边推1:美元和马克)

题目描述

今天 6:00 起床,我转身发现枕头边有 100100 美元。

出门的时候发现门口有家冰淇淋店,拉了很长的横幅:“今天 100100 美元和 400400 马克互换”

第二天的横幅是:“今天 100100 美元和 300300 马克互换”

第三天的横幅是:“今天 100100 美元和 500500 马克互换”

第四天的横幅是:“今天 100100 美元和 300300 马克互换”

第五天的横幅是:“今天 100100 美元和 250250 马克互换”

第五天的晚上,我灵光一闪,决定坐时光飞机回到第一天的上午 6:00,准备发大财!

我是这么做的:

Day 1 ... 用 100.0000100.0000 美元换 400.0000400.0000 马克。

晚上我手里拿着 400.0000400.0000 马克安心睡觉了。

Day 2 ... 用 400.0000400.0000 马克换 133.3333133.3333 美元。

晚上我手里拿着 133.3333133.3333 美元安心睡觉了。

Day 3 ... 用 133.3333133.3333 美元换 666.6666666.6666 马克。

晚上我手里拿着 666.6666666.6666 马克安心睡觉了。

Day 4 ... 我手里拿着 666.6666666.6666 马克不换美元,因为我知道明天换更好呀。

晚上我手里拿着 666.6666666.6666 马克安心睡觉了。

Day 5 ... 用 666.6666666.6666 马克 换 266.6666266.6666 美元。

晚上我手里拿着 266.6666266.6666 美元偷笑,我赚了 166.6666166.6666 美元。厉害吧?你有时光机吗?

第六天全世界都不使用马克了,所以最后一天留在手里的必须是美元!

输入格式

第一行是一个自然数 NN,表示天数。

接下来的 NN 行中每行是一个自然数 aia_i

表示预先知道的第 ii100100 美元和 aia_i 马克能互换。

输出格式

一行,即最后一天晚上手里的美元数目(保留两位小数)。

5
400
300
500
300
250
266.67

数据规模与约定

1N1001\le N\le 1001ai10001\le a_i\le 1000