题解 P1968 【美元汇率】

2er0n3 · 2017-10-29 10:49:15 · 题解

蒟蒻题解奉上；

我用的动态规划思想，先设置f [ x ] [ 0 ]:表示第x天美元的最大收益；f [ x ] [ 1 ]表示第x天马克最大收益

先初始化f[ 1 ] [ 0 ] =100 ; f [ 1 ] [ 1 ]=第一天的汇率；

于是可得出状态转移方程f[i][0]=max(f[i-1][0],(f[i-1][1]/a[i])*100);

f[i][1]=max(f[i-1][1],f[i-1][0]*a[i]/100);

最后输出时再比较一次大小即可（要把马克转为美元哦）；

代码奉上（神犇dalao多多指教）

#include<iostream>
#include<cstdio>
int n,a[100000];
double f[10000][2];//不要忘记double !!! 
using namespace std;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    f[1][0]=100;
    f[1][1]=a[1];//初始化千万不要忘记!!!! 
    for(int i=2;i<=n;i++)//f[x][0]为美元，f[x][1]为马克； 
    {
        f[i][0]=max(f[i-1][0],(f[i-1][1]/a[i])*100);// 
        f[i][1]=max(f[i-1][1],f[i-1][0]*a[i]/100);
    }
    printf("%.2f",max(f[n][0],(f[n][1]/a[n])*100));//比较把马克转为美元 
    return 0;
}