#P1064. 动态规划入门(一维一边推1:美元和马克)
动态规划入门(一维一边推1:美元和马克)
题目描述
今天 6:00 起床,我转身发现枕头边有 美元。
出门的时候发现门口有家冰淇淋店,拉了很长的横幅:“今天 美元和 马克互换”
第二天的横幅是:“今天 美元和 马克互换”
第三天的横幅是:“今天 美元和 马克互换”
第四天的横幅是:“今天 美元和 马克互换”
第五天的横幅是:“今天 美元和 马克互换”
第五天的晚上,我灵光一闪,决定坐时光飞机回到第一天的上午 6:00,准备发大财!
我是这么做的:
Day 1 ... 用 美元换 马克。
晚上我手里拿着 马克安心睡觉了。
Day 2 ... 用 马克换 美元。
晚上我手里拿着 美元安心睡觉了。
Day 3 ... 用 美元换 马克。
晚上我手里拿着 马克安心睡觉了。
Day 4 ... 我手里拿着 马克不换美元,因为我知道明天换更好呀。
晚上我手里拿着 马克安心睡觉了。
Day 5 ... 用 马克 换 美元。
晚上我手里拿着 美元偷笑,我赚了 美元。厉害吧?你有时光机吗?
第六天全世界都不使用马克了,所以最后一天留在手里的必须是美元!
输入格式
第一行是一个自然数 ,表示天数。
接下来的 行中每行是一个自然数 。
表示预先知道的第 天 美元和 马克能互换。
输出格式
一行,即最后一天晚上手里的美元数目(保留两位小数)。
5
400
300
500
300
250
266.67
数据规模与约定
,。