CF391F3 Stock Trading

本题分为三个子问题：解决子问题 F1 得 8 分，F2 得 15 分，F3 得 10 分。 Manao 开发了一个模型，可以预测未来 $n$ 天内某公司股票的价格，他想设计一个算法来最大化交易利润。不过，Manao 的交易账户有以下限制： - 任何时候最多只能持有一股或零股该股票； - 每天只能做一次买入或卖出操作； - 在接下来的 $n$ 天内最多允许进行 $k$ 次买入操作； 在本题中，我们将一次交易定义为：在第 $i$ 天以某个价格买入一股股票，然后持有到某个 $j > i$ 的天数时卖出。Manao 被允许在 $n$ 天内进行最多 $k$ 次不重叠的交易，而他的模型可以准确预测股票每天的价格。 虽然这些限制可能影响利润的最大化，但因为 Manao 的模型预测非常精准，他仍然可以赚取大量收益。例如，Manao 可以等到价格低时买入，等到价格高时卖出，这一过程最多可重复 $k$ 次，直到 $n$ 天结束。 然而，Manao 不仅仅满足于一个普通的交易策略，他希望找到一个在这些限制条件下的最佳交易策略。请帮助 Manao，写出一个程序，在 $n$ 天的交易期内，在这些限制下，找出何时进行买卖可以获得最大的潜在利润。

第一行为两个整数 $n$ 和 $k$，用空格分隔，分别表示天数和最大买入次数，满足 $1 \le n \le 4000000, 1 \le k \le 200000$。接下来的 $n$ 行，每行包含一个整数 $p_i$，表示第 $i$ 天的股票价格，且价格范围是 $0 \le p_i \le 10^{12}$。 本题包含三个子问题，不同子问题有不同的输入限制，正确解答子问题可获得对应分数： - 子问题 F1（8 分）：$n$ 的范围是 $1$ 到 $3000$； - 子问题 F2（15 分）：$n$ 的范围是 $1$ 到 $100000$； - 子问题 F3（10 分）：$n$ 的范围是 $1$ 到 $4000000$。

程序输出一个整数，表示在 $n$ 天内，在不持有股票、任何时候最多持有一股的情况下，经过最多 $k$ 次交易，能够获得的最大利润。

第一个示例中，最佳的两笔交易是： 1. 第 9 天以价格 1 买入，第 10 天以价格 9 卖出； 2. 第 1 天以价格 2 买入，第 4 天以价格 9 卖出。 这两笔交易不重叠，因此都可以进行，总利润为 $(9-2) + (9-1) = 15$。 示例交易为： ``` 2 | 7 | 3 | 9 | 8 | 7 | 9 | 7 | 1 | 9 买入 | | | 卖出 | | | | | 买入 | 卖出 ``` 第二个示例中，即便可以进行 5 笔交易，但只有 4 笔交易有利可图，第五笔交易反而会导致亏损，所以只进行以下 4 笔： ``` 2 | 7 | 3 | 9 | 8 | 7 | 9 | 7 | 1 | 9 买入 | 卖出 | 买入 | 卖出 | | 买入 | 卖出 | | 买入 | 卖出 ``` 总利润为 $(7-2) + (9-3) + (9-7) + (9-1) = 21$。 **本翻译由 AI 自动生成**