EXCHANGE(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 马克
【思路剖析】
第一种:f[i][j][0..1]为到第i天为止,在第i天,使用第j种方法(1=马克到美元 2=美元到马克 3=不换)的最大收益,第三维表示手上是哪种钱。
第二种:f[i][0]为第i天,马克到美元,f[i][1]为第i天,美元到马克,f[i][0]=f[1..i-1][1]
【代码日志】
<
pre class="lang:default decode:true " title="EXCHANGE 版本1 WA(一定要看清楚题目!)" >#include<bits/stdc++.h>
using namespace std;
//---------题目变量
int n,m100_d[105],d100_m[105];
//---------自用变量
float dp[105][4];
//0=马克到美元,手上拿着美元 1=美元到马克,手上拿着马克
//2=不换,手上拿着马克 3=不换,手上拿着美元
//---------主程序
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>m100_d[i]>>d100_m[i];
for(int j=0;j<4;j++){
dp[i][j]=-1;
}
}
for(int j=0;j<4;j++){
dp[0][j]=-1;
}
dp[0][2]=100;
for(int i=1;i<=n;i++){
cout<<"dp["<<i-1<<"][0] = "<<dp[i-1][0]<<endl;
if(dp[i-1][0]!=-1){
//手上拿着美金 就是这里 误认为是100美元换S马克
if(dp[i][1]<dp[i-1][0]/100d100_m[i])dp[i][1]=dp[i-1][0]/100d100_m[i];
if(dp[i][3]<dp[i-1][0])dp[i][3]=dp[i-1][0];
}
if(dp[i-1][1]!=-1){
//手上拿着马克
if(dp[i][0]<dp[i-1][1]/100m100_d[i])dp[i][0]=dp[i-1][1]/100m100_d[i];
if(dp[i][2]<dp[i-1][1])dp[i][2]=dp[i-1][1];
}
if(dp[i-1][2]!=-1){
//手上拿着马克
if(dp[i][0]<dp[i-1][2]/100m100_d[i])dp[i][0]=dp[i-1][2]/100m100_d[i];
if(dp[i][2]<dp[i-1][2])dp[i][2]=dp[i-1][2];
}
if(dp[i-1][3]!=-1){
//手上拿着美金 就是这里 误认为是100美元换S马克
if(dp[i][1]<dp[i-1][3]/100d100_m[i])dp[i][1]=dp[i-1][3]/100d100_m[i];
if(dp[i][3]<dp[i-1][3])dp[i][3]=dp[i-1][3];
}
}
float ans=-1;
if(ans<dp[n][1]){
ans=dp[n][1];
}
if(ans<dp[n][2]){
ans=dp[n][2];
}
cout<<ans<<endl;
return 0;
}
<
pre class="lang:default decode:true " title="版本2(看上去总算对一点了)" >#include<bits/stdc++.h>
using namespace std;
//---------题目变量
int n,m100_d[105],d100_m[105];
//---------自用变量
float dp[105][4];
//0=马克到美元,手上拿着美元 1=美元到马克,手上拿着马克
//2=不换,手上拿着马克 3=不换,手上拿着美元
//---------主程序
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>m100_d[i]>>d100_m[i];
for(int j=0;j<4;j++){
dp[i][j]=-1;
}
}
for(int j=0;j<4;j++){
dp[0][j]=-1;
}
dp[0][2]=100;
for(int i=1;i<=n;i++){
cout<<"dp["<<i-1<<"][0] = "<<dp[i-1][0]<<endl;
if(dp[i-1][0]!=-1){
//手上拿着美金
if(dp[i][1]<dp[i-1][0]100/d100_m[i])dp[i][1]=dp[i-1][0]100/d100_m[i];
if(dp[i][3]<dp[i-1][0])dp[i][3]=dp[i-1][0];
}
if(dp[i-1][1]!=-1){
//手上拿着马克
if(dp[i][0]<dp[i-1][1]/100m100_d[i])dp[i][0]=dp[i-1][1]/100m100_d[i];
if(dp[i][2]<dp[i-1][1])dp[i][2]=dp[i-1][1];
}
if(dp[i-1][2]!=-1){
//手上拿着马克
if(dp[i][0]<dp[i-1][2]/100m100_d[i])dp[i][0]=dp[i-1][2]/100m100_d[i];
if(dp[i][2]<dp[i-1][2])dp[i][2]=dp[i-1][2];
}
if(dp[i-1][3]!=-1){
//手上拿着美金
if(dp[i][1]<dp[i-1][3]100/d100_m[i])dp[i][1]=dp[i-1][3]100/d100_m[i];
if(dp[i][3]<dp[i-1][3])dp[i][3]=dp[i-1][3];
}
}
float ans=-1;
if(ans<dp[n][1]){
ans=dp[n][1];
}
if(ans<dp[n][2]){
ans=dp[n][2];
}
cout<<setiosflags(ios::fixed)<<setprecision(2)<<ans<<endl;
return 0;
}