BSOJ1040 -- 【练习题目】美元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.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 美元

---

设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
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
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;
}

转载于:https://www.cnblogs.com/NOI-AKer/p/Dollars.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！