【2018寒假集训 Day2】【动态规划】钱币兑换(exchange)(自己翻译的2333)
钱币兑换(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;
}
最新文章
- berkeley db replica机制 - 主从同步
- Android handler.obtainMessage()
- Java的native关键字---JAVA下调用其他语言的关键词
- Python学习-使用matplotlib画动态多图
- memcached 命令操作详解
- Django学习报错记录
- 我的第一个python web开发框架(7)——本地部署前端访问服务器
- 聚类-31省市居民家庭消费水平-city
- myecplise ssh项目配置上遇到的问题
- 简单比较init-method,afterPropertiesSet和BeanPostProcessor
- Entity Framework 学习总结之十一:POCO
- [ZZ] 基于Matlab的标记分水岭分割算法
- wdk驱动开发的特点
- JavaScript之BOM五大对象(window;location;navigator;screen;history)
- [C++]指针与引用(定义辨析)
- topcoder srm 696 div1 -3
- Requests库入门
- a标签点击后,保证后来的样式
- android的几种“通知”方式简单实现(Notification&;NotificationManager)
- 重温SQL——行转列,列转行