洛谷 p1968 美元汇率 题解

传送门

美元由马克转化,马克由美元转化

求最大美元

每一天只有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[],w[];

int main() {

    scanf("%d",&m);

    for(i=; i<=m; i++) {

        scanf("%lf",&w[i]);

    }

    f[]=;

     for(i=; i<=m; ++i) {

         double yy=f[];//要写这个,不然会错

        f[]=max(f[],f[]/w[i]*100.000);

        f[]=max(f[],yy*w[i]/100.000);//f[2]只能由上一次的f[1](即yy)转换

    }

    printf("%.2lf",f[]);

    return ;

}