美元汇率

题意

戴维初始有 100 美元。接下来 N 天，每天有一个汇率 R（100 美元 = R 马克）。每天他可以选择：

不操作，继续保持当前货币；
把手上的全部美元按 R/100 换成马克；
把手上的全部马克按 100/R 换成美元。

求第 N 天结束时最多能持有多少美元。

思路

最直接的想法是枚举每一天「换」还是「不换」，共 2^(N-1) 种可能。N 稍大就不可行。

先看一个可以直接验证想法的朴素解（适用于小数据）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46// brute.cpp：小数据暴力枚举，用来帮助理解题意并辅助对拍。
// 时间复杂度 O(2^N)，只适合 N <= 10。

#include <bits/stdc++.h>
using namespace std;

int n;
double rate[105]; // rate[i] 表示第 i 天的汇率：100 美元 = rate[i] 马克

// 枚举所有兑换方案。
// day：当前在第几天（1-indexed）
// money：当前持有的金额
// has_dollar：true 表示当前持有美元，false 表示持有马克
double dfs(int day, double money, bool has_dollar) {
    if (day > n) {
        // 最后一天结束，如果还持有马克则按最后一天的汇率换回美元
        if (has_dollar) return money;
        else return money * 100.0 / rate[n];
    }
    double r = rate[day];
    // 不兑换，继续持有当前货币
    double best = dfs(day + 1, money, has_dollar);
    // 兑换全部资金
    if (has_dollar) {
        // 美元 -> 马克
        best = max(best, dfs(day + 1, money * r / 100.0, false));
    } else {
        // 马克 -> 美元
        best = max(best, dfs(day + 1, money * 100.0 / r, true));
    }
    return best;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> rate[i];
    }

    double ans = dfs(1, 100.0, true);
    cout << fixed << setprecision(2) << ans << "\n";
    return 0;
}

这个 DFS 枚举了所有兑换决策序列，时间复杂度为 O(2^N)，只适合 N ≤ 10 的小规模验证。

瓶颈：指数级分支太多。

关键观察：每天结束时只有两种状态——持有美元或持有马克。第 i 天的最优值只依赖第 i-1 天的最优值，与具体决策路径无关。

优化方案：两状态线性 DP。

text

1
2
3
4
5dollar = 100, mark = 0
for 每天汇率 r:
    new_dollar = max(dollar, mark × 100 / r)
    new_mark   = max(mark,   dollar × r / 100)
    dollar = new_dollar, mark = new_mark

每天用当天汇率尝试「不换」和「换」两种可能，取较大值更新两个状态。整个过程只需要 O(N) 时间。

正确性证明：

设 $U_i$ 为第 $i$ 天结束时持有美元的最大美元数， $M_i$ 为持有马克的最大马克数。

第 $i+1$ 天汇率 $r_{i+1}$ 固定，当天结束时持有美元的候选值只有两个：

昨天持有美元且不换 $\to U_i$
昨天持有马克且兑换 $\to M_i \times \frac{100}{r_{i+1}}$

两者都是 $U_i, M_i$ 的线性单调函数，因此 $U_i$ 和 $M_i$ 越大，候选值也越大。这意味着第 $i$ 天结束时只需保留两个状态的最大值——任何被抛弃的次优路径都不可能在第 $i+1$ 天反超最优路径。

持有马克的推理同理。归纳成立，最终 $U_N$ 即为答案。

DP 公式

设 $U_i$ 表示第 $i$ 天结束时持有美元的最大美元数， $M_i$ 表示第 $i$ 天结束时持有马克的最大马克数。若第 $i$ 天汇率为 $r_i$ ，则：

U_i=\max\left(U_{i-1},\ \frac{100M_{i-1}}{r_i}\right)

M_i=\max\left(M_{i-1},\ \frac{U_{i-1}r_i}{100}\right)

初始为：

U_0=100,\quad M_0=0

最终输出 $U_n$ 。

公式解释：每天结束只需要保留两个最优状态：手里全是美元，或手里全是马克。新状态来自“不换”和“当天按汇率兑换”两种选择，取最大值即可；因为兑换公式对已有金额单调，次优金额不可能反超。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33#include <bits/stdc++.h>
using namespace std;

int n;
double rate[105]; // rate[i] 表示第 i 天的汇率：100 美元 = rate[i] 马克

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> rate[i];
    }

    // dollar：以美元结尾的最大美元价值
    // mark：以马克结尾的最大马克价值
    double dollar = 100.0;
    double mark = 0.0;

    for (int i = 1; i <= n; i++) {
        double r = rate[i];
        // 当天结束时持有美元：要么昨天就持有美元（不动），要么昨天持有马克并在今天兑换
        double new_dollar = max(dollar, mark * 100.0 / r);
        // 当天结束时持有马克：要么昨天就持有马克（不动），要么昨天持有美元并在今天兑换
        double new_mark = max(mark, dollar * r / 100.0);
        dollar = new_dollar;
        mark = new_mark;
    }

    cout << fixed << setprecision(2) << dollar << "\n";
    return 0;
}

复杂度

时间复杂度：O(N)，一次遍历即可。
空间复杂度：O(1)（滚动变量）或 O(N)（存储汇率数组）。

总结

本题是一个经典的两状态 DP 入门题，核心是认识到只有两种货币状态、每天最多只有一个兑换动作，因此可以用简单的线性递推代替指数枚举。类似的「两状态切换」模型也适用于股票买卖系列的部分简单版本。

从结构上看，本题和 LIS（最长上升子序列）有相同的 DP 本质：最后一个人的最优值依赖前面人的最优值。区别在于 LIS 的每个位置需要检查所有前面的位置（ $O(n^2)$ ），而本题只有两个状态，转移是 $O(1)$ 的。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

目录

题意

思路

DP 公式

代码

复杂度

总结

一图流解析