美元和马克(dp)

【问题描述】
今天6:00起床，我转身发现枕头边有100美元。
出门的时候发现门口有家冰淇淋店，拉了很长的横幅：“今天100美元和400马克互换”
第二天的横幅是：“今天100美元和300马克互换”
第三天的横幅是：“今天100美元和500马克互换”
第四天的横幅是：“今天100美元和300马克互换”
第五天的横幅是：“今天100美元和250马克互换”

第五天的晚上，我灵光一闪，决定坐时光飞机回到第一天的上午6:00，准备发大财！
我是这么做的：
Day 1 ... 用 100.0000 美元 换 400.0000 马克
晚上我手里拿着400.0000马克安心睡觉了

Day 2 ... 用 400.0000 马克 换 133.3333 美元
晚上我手里拿着133.3333美元安心睡觉了

Day 3 ... 用 133.3333 美元 换 666.6666 马克
晚上我手里拿着666.6666马克安心睡觉了

Day 4 ... 我手里拿着666.6666 马克 不换美元，因为我知道明天换更好呀
晚上我手里拿着666.6666马克安心睡觉了

Day 5 ... 用 666.6666 马克 换 266.6666 美元
晚上我手里拿着266.6666美元偷笑，我赚了166.6666美元。厉害吧？你有时光机吗？

第六天全世界都不使用马克了，所以最后一天留在手里的必须是美元！


【输入文件】
第一行是一个自然数N，1≤N≤100，表示天数。
接下来的N行中每行是一个自然数a[i]，1≤a[i]≤1000。
表示预先知道的第i天100美元 和 A马克 能互换。
 
【输出文件】
一行,即最后一天晚上手里的美元数目(保留两位小数)。

解题思路：

dp1[i]代表前i天可以兑换出的最多美元，dp2[i]代表前i天可以兑换出的最多马克，可以很容易得出转移方程，

就是将前i-1天的另一种货币用当天的兑换比例转换过来与前i-1天同种货币比较就可以了。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<stdio.h>
#include<math.h>
#include<cstdlib>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#define ll long long int
#define INF 0x7fffffff
#define mod 1000000007
#define me(a,b) memset(a,b,sizeof(a))
#define PI acos(-1.0)
#define mian main
//size_t npos=-1;
//ios::sync_with_stdio(0),cin.tie(0);
using namespace std;
const int N=1e5+5;
 
int main()
{
    double dp1[105],dp2[105],a[105];
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    dp1[0]=100;
    dp2[0]=0;
    for(int i=1;i<=n;i++){
        dp1[i]=max(dp2[i-1]/a[i]*(double)100,dp1[i-1]);
        dp2[i]=max(dp1[i-1]/(double)100*a[i],dp2[i-1]);
    }
    cout<<setprecision(2)<<std::fixed<<dp1[n]<<endl;
}