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