钱币兑换(exchange)
问题描述:
Dave偶然获得了未来几天的美元(dollars)与马克(marks)之间的兑换率。例如Dave开始有100marks，请编写个程序帮助Dave找出最好的买卖marks或dollars的方案，使Dave最后一天有最多的marks。
输入格式：
输入文件的第一行有个自然数N, 1 ≤ N ≤ 100,表示Dave知道未来兑换率的天数。
下面N行每行有两个被空格分隔的自然数B和S， 100 ≤ B ≤ S ≤ 1000。第(i＋1)行表示的和是第 i天的兑换率，表示这一天： 100个marks 可以买B个dollars，和S个dollars可以买100个marks。
输出格式：
只一行一个实数，表示最多可获得的marks，精确到小数后2位。
输入输出样例：
exchange.in
3
393 398
394 401
386 386
exchange.out
102.07
exchange.in
5
300 300
310 320
320 330
330 330
300 320
exchange.out
103.12
exchange.in
8
218 219
228 231
227 235
205 213
230 232
239 239
251 258
205 213
exchange.out
126.14
样例3的解释 (此处不用输出)
第1天： 100.0000 马克换成 228.0000 美元
第4天： 228.0000 美元换成 107.0422 马克
第7天： 107.0422 马克换成 268.6760美元
第8天： 268.6760 美元换成 126.1389 马克
【解题思路】
首先分天数为阶段，每一天手上的钱的多少由前一天手上的钱决定，要求如何拥有最多的马克，显然可以利用动态规划解题。
但是每一天的钱有一个单位，所以显然用一个一维数组来进行动态规划是不行的，
显然，根据钱币之间的兑换公式，可以写出状态转移方程。
f1[i]=max(f1[i-1],f2[i-1]/s[i]*100);//马克
f2[i]=max(f2[i-1],f1[i-1]*b[i]/100);//美元【参考程序】
#include<iostream>
#include<cstdio>
#include<iomanip>
using namespace std;
int n,b[101],s[101];
double f1[101],f2[101];
int main()
{
freopen("exchange.in","r",stdin);
freopen("exchange.out","w",stdout);
cin>>n;
f1[0]=100;//初始有100马克
f2[0]=0;//有0美元
for (int i=1;i<=n;i++) cin>>b[i]>>s[i];
f1[1]=100;//第一天最多有100马克
f2[1]=b[1];//最多有b[1]美元
for (int i=2;i<=n;i++)
{
f1[i]=max(f1[i-1],f2[i-1]/s[i]*100);
f2[i]=max(f2[i-1],f1[i-1]*b[i]/100);
//动态规划
}
cout<<fixed<<setprecision(2)<<max(f1[n],f2[n]/s[n]*100);//保留小数位，求最大值
return 0;
}