洛谷P1968 美元汇率【DP】【橙】

美元汇率【DP】【橙】"/>

洛谷P1968 美元汇率【DP】【橙】

Date：2021.12.28

题意：开始有100美元，有n天每天都有一个汇率，表示100美元能转换为多少马克，求过n天后最多能得到多少美元。

思路：我们首先考虑美元是不应该分批的，因为dp中一定存在最优解，因此在最优方案上全部梭哈一定赚得钱最多。其次因为每一步都要考虑哪个到哪个转换或者是保持原来状态不转换，因此用状态0、1分别表示两个情况。（注意开double）
①f[i][0]：第i天结束后最多获得多少美元。
②f[i][1]：第i天结束后最多获得多少马克。
每天都可以变或不变，因此状态转移如下：
①f[i][0]=max(f[i-1][0],f[i-1][1]/a[i]);
②f[i][1]=max(f[i-1][1],f[i-1][0]*a[i]);
代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 210;
LL n,m,k,t;
LL a[N]