题目链接：
http://tyvj.cn/p/1095
https://www.luogu.org/problem/show?pid=1968
描述
在以后的若干天里戴维将学习美元与德国马克的汇率。编写程序帮助戴维何时应买或卖马克或美元，使他从100美元开始，最后能获得最高可能的价值。
输入格式
输入文件的第一行是一个自然数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美元。
输出格式
输出文件的第一行也是唯一的一行应输出要求的钱数(单位为美元，保留两位小数)。
测试样例1
输入
5
400
300
500
300
250
输出
266.67
备注
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 美元
解题思路（http://tyvj.cn/Solution/6521）
AC代码：
1 #include <stdio.h> 2 int main(void) 3 { 4 int i,n; 5 double a[3],sum; 6 scanf("%d",&n); 7 sum = 100; 8 scanf("%lf%lf",&a[0],&a[1]); 9 for (i=0;i<n-1;i++) 10 { 11 if (a[0] > a[1]) 12 sum *= (double)a[0]/a[1]; 13 scanf("%lf",&a[2]); 14 a[0]=a[1]; 15 a[1]=a[2]; 16 } 17 printf("%.2lf\n",sum); 18 return 0; 19 }
可以参考阅读的代码（一）：
1 #include <stdio.h> 2 #define max_data 100 3 int main(void) 4 { 5 int i; 6 int n; 7 int a[max_data]; 8 double sum; 9 scanf("%d",&n); 10 11 for (i = 0;i < n;++i) 12 scanf("%d",a + i); 13 sum = 100; 14 15 for (i = 0;i < n - 1;++i) 16 if (a[i] > a[i + 1]) 17 sum *= (double) a[i] / a[i + 1]; 18 19 printf("%.2lf\n",sum); 20 21 return 0; 22 }
可以参考阅读的代码（二）：
来源：http://blog.csdn.net/wxf1995/article/details/6007723#
1 #include<stdio.h> 2 #include<iostream> 3 using namespace std; 4 const int N=100; 5 double ans[N+1][2];//0维表示美元 1维表示马克 6 double num[N+1];//num[i]的马克可以在第i天换100美元 7 int n; 8 void input() 9 { 10 scanf("%d",&n); 11 for (int i=1;i<=n;i++) 12 { 13 scanf("%lf",&num[i]); 14 } 15 return; 16 } 17 void prime() 18 { 19 ans[0][0]=100.0; 20 for (int i=1;i<=n;i++) 21 { 22 ans[i][0]=ans[i-1][0]; 23 ans[i][1]=ans[i-1][1]; 24 for (int j=1;j<i;j++) 25 { 26 ans[i][0]=max(ans[j][1]/num[i]*100.0,ans[i][0]);//换成美元 27 } 28 for (int j=0;j<i;j++) 29 { 30 ans[i][1]=max(ans[j][0]*num[i]/100.0,ans[i][1]);//换成马克 31 } 32 } 33 printf("%.2lf",ans[n][0]); 34 return; 35 } 36 int main() 37 { 38 input(); 39 prime(); 40 return 0; 41 }
本代码解析：
每一天所能拥有的最大的价值肯定要么是全马克，要么全是美元（不解释）
所以可以记录第i天所能拥有的最大马克数和美元数，来递推
ans[i][1]表示第i天所能拥有的最多的马克
ans[i][0]表示第i天所能拥有的最多的美元
自然
ans[i][1]=ans[i-1][1];
ans[i][1]=max(ans[j][0]*num[i]/100.0,ans[i][1]);//换成马克
ans[i][0]也同理
