Description
在以后的若干天里戴维将学习美元与德国马克的汇率。编写程序帮助戴维何时应买或卖马克或美元,使他从100美元开始,最后能获得最高可能的价值。
Input
输入文件的第一行是一个自然数N,1≤N≤100,表示戴维学习汇率的天数。
接下来的N行中每行是一个自然数A,1≤A≤1000。第i+1行的A表示预先知道的第i+1天的平均汇率,在这一天中,戴维既能用100美元买A马克也能用A马克购买100美元。
接下来的N行中每行是一个自然数A,1≤A≤1000。第i+1行的A表示预先知道的第i+1天的平均汇率,在这一天中,戴维既能用100美元买A马克也能用A马克购买100美元。
Output
输出文件的第一行也是唯一的一行应输出要求的钱数(单位为美元,保留两位小数)。
注意:考虑到实数算术运算中进位的误差,结果在正确结果0.05美元范围内的被认为是正确的,戴维必须在最后一天结束之前将他的钱都换成美元。
注意:考虑到实数算术运算中进位的误差,结果在正确结果0.05美元范围内的被认为是正确的,戴维必须在最后一天结束之前将他的钱都换成美元。
Sample Input
5
400
300
500
300
250
Sample Output
266.67
Hint
【样例解释】:(无需输出)
Day 1 ... changing 100.0000 美元 = 400.0000 马克
Day 2 ... changing 400.0000 马克 = 133.3333 美元
Day 3 ... changing 133.3333 美元 = 666.6666 马克
Day 5 ... changing 666.6666 马克 = 266.6666 美元
Day 1 ... changing 100.0000 美元 = 400.0000 马克
Day 2 ... changing 400.0000 马克 = 133.3333 美元
Day 3 ... changing 133.3333 美元 = 666.6666 马克
Day 5 ... changing 666.6666 马克 = 266.6666 美元
设f[i][0]为第i天最多美元数量,f[i][1]为为第i天最多马克数量,初始化f[1][0]=100,f[1][1]=f[i][0]/100.*a[i]=a[i]
模拟,易得DP做法:
#include<bits/stdc++.h> using namespace std; #define why 105 int n,a[why]; double f[why][2]; inline int redn() { int ret=0,f=1; char ch=getchar(); while(!isdigit(ch)) { f=(ch!='-')?f:-f; ch=getchar(); } while(isdigit(ch)) { ret=ret*10+ch-'0'; ch=getchar(); } return f>0?ret:-ret; } int main() { n=redn(); for(int i=1;i<=n;++i)a[i]=redn(); f[1][0]=100; f[1][1]=a[1]; for(int i=2;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]/100.*a[i]); } printf("%.2lf",max(f[n][0],f[n][1]/a[n]*100.)); return 0; }
为了省空间,去掉f数组和a数组,边输入边做,用临时变量储存值,如下:
#include<bits/stdc++.h> using namespace std; #define why 105 int n,a; double f0=100.,f1,f; inline int redn() { int ret=0,f=1; char ch=getchar(); while(!isdigit(ch)) { f=(ch!='-')?f:-f; ch=getchar(); } while(isdigit(ch)) { ret=ret*10+ch-'0'; ch=getchar(); } return f>0?ret:-ret; } int main() { n=redn(); a=redn(); f1=a; for(int i=2;i<=n;++i) { a=redn(); f=f0;//f0会被修改,用f存值 f0=max(f0,f1/a*100.); f1=max(f1,f/100.*a); } printf("%.2lf",max(f0,f1/a*100.)); return 0; }