【DP练习】美元DOLLARS

1040 – 【练习题目】美元DOLLARS
Description
在以后的若干天里戴维将学习美元与德国马克的汇率。编写程序帮助戴维何时应买或卖马克或美元，使他从100美元开始，最后能获得最高可能的价值。
Input
输入文件的第一行是一个自然数N，1≤N≤100，表示戴维学习汇率的天数。
接下来的N行中每行是一个自然数A，1≤A≤1000。第i+1行的A表示预先知道的第i+1天的平均汇率，在这一天中，戴维既能用100美元买A马克也能用A马克购买100美元。
Output
输出文件的第一行也是唯一的一行应输出要求的钱数(单位为美元，保留两位小数)。
注意：考虑到实数算术运算中进位的误差，结果在正确结果0.05美元范围内的被认为是正确的，戴维必须在最后一天结束之前将他的钱都换成美元。
Sample Input
5
400
300
500
300
250
Sample Output
266.66(oj上此题样例输出有误，输出应为266.67)
题目链接：https://oj.bashu.com.cn/code/problempage.php

看完这道题，我们先来了解一下
美元和马克的样子


【温馨提示】
本题无Special Judge,所以题面中的


【题目分析】:
读完题感觉
所以显然，此题为水题
我们先来了解一下什么是汇率
根据政治书的描述，
汇率汇率又称汇价，是两种货币之间的兑换比率；保持人民币币值基本稳定，即对内保持物价总水平稳定，对外保持人民币汇率稳定，对人民生活安定，经济社会持续健康发展，对世界金融稳定，经济发展具有重要意义。

言归正传，本题用动态规划解决。
每一天手中的钱只有两种情况:
① 直接继承前一天的该货币
② 从前一天的另一种货币兑换过来
所以
设f[i,0]表示第i天所能得到的美元最大收益；
f[i,1]表示第i天所能得到的马克最大收益；
则根据题意，
状态转移方程就是

f[i][0]=max(f[i-1][0],(f[i-1][1]/a[i])*100); f[i][1]=max(f[i-1][1],f[i-1][0]*a[i]/100);
初始状态：f[i,0]=100,f[i,1]=0；
Ans=f[n,0];（题目要求最后必须是美元）

#include<iostream>
#include<cstdio>
using namespace std;
int N;
double f[105][2],a[105];
int main()
{int i;cin>>N;for(i=1;i<=N;i++)cin>>a[i];f[0][0]=100;for(i=1;i<=N;i++){f[i][0]=max(f[i-1][0],(f[i-1][1]/a[i])*100);f[i][1]=max(f[i-1][1],(f[i-1][0]*a[i])/100);}printf("%.2lf\n",f[N][0]);return 0;
}