EXCHANGE(动态规划练习) 解题日志

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

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注