美元由马克转化,马克由美元转化
求最大美元
每一天只有2种选择
①:不转化另一货币
②:转化另一货币
典型01背包
可以开一个二维数组f[100][3]
F[i][1]表示前i天获得最大美元
F[i][2]表示前i天获得最大马克
F[i][1]=max(f[i-1][1],f[i-1][2]/w[i]*100.000);
F[i][2]=max(f[i-1][2],yy*w[i]/100.000);
/100.000的目的是保证精度
这个题也要注意保证精度
最终答案当然是f[最大天数][1];
我们发现第一维都没用
当然也可以压维啦~
当然也要注意,因为只能由上一天转换
#include<bits/stdc++.h> using namespace std; int i,m; double f[3],w[1001]; int main() { scanf("%d",&m); for(i=1; i<=m; i++) { scanf("%lf",&w[i]); } f[1]=100; for(i=1; i<=m; ++i) { double yy=f[1];//要写这个,不然会错 f[1]=max(f[1],f[2]/w[i]*100.000); f[2]=max(f[2],yy*w[i]/100.000);//f[2]只能由上一次的f[1](即yy)转换 } printf("%.2lf",f[1]); return 0; }