CF391F2 Stock Trading

本题由三个子问题组成：完成子问题 F1 可获得 8 分，完成子问题 F2 可获得 15 分，完成子问题 F3 可获得 10 分。 Manao 开发了一种预测模型，可以准确预测未来 $n$ 天内某公司的股票价格。他希望设计一套能够利用这些预测盈利最大化的交易算法。然而，他的交易账户受到以下限制： - 每次只能持有 0 股或 1 股股票； - 每天只允许进行一次买入或卖出操作； - 在接下来的 $n$ 天中最多可进行 $k$ 次买入操作； 在本题中，我们定义了一笔交易，即在第 $i$ 天买入一股股票，持有至第 $j$ 天 ($j > i$) 再卖出。基于上述限制，Manao 在这 $n$ 天内最多可以执行 $k$ 笔不重叠的交易。 尽管这些限制似乎减少了 Manao 的潜在盈利，与能够进行无限次交易或持有多股股票相比，但由于他的模型可以准确预测每天股价，Manao 仍然有机会获得可观的利润。比如，当股价较低时买入，然后在股价较高时卖出，重复这一操作，最多可进行 $k$ 次，直至 $n$ 天结束。 然而，Manao 不仅满足于目前已有的盈利算法，他希望在这些限制条件下找到最优的交易策略。请帮助 Manao 编写一个程序，确定何时买入和卖出股票，以在这 $n$ 天内实现最大利润。

第一行输入包含两个整数 $n$ 和 $k$，用空格隔开，其中 $1 \leq n \leq 4000000, 0 \leq k \leq 200000$。接下来的 $n$ 行，每行包含一个整数 $p_i$，表示第 $i$ 天股票的价格，满足 $0 \leq p_i \leq 10^{12}$。 题目分为以下三个子问题，不同的子问题有不同的输入规模限制： - 子问题 F1（8 分）：$n$ 在 1 到 3000 之间。 - 子问题 F2（15 分）：$n$ 在 1 到 100000 之间。 - 子问题 F3（10 分）：$n$ 在 1 到 4000000 之间。

你的程序只需输出一个整数，即在未来 $n$ 天内，Manao 在从无股票开始，有最多 $k$ 次买入机会，始终持有 0 或 1 股股票的情况下，所能获得的最大利润。

在第一个示例中，最优的两笔交易是：第 9 天以价格 $1$ 买入，第 10 天以价格 $9$ 卖出；以及第 1 天以价格 $2$ 买入，第 4 天以价格 $9$ 卖出。这两笔交易互不冲突，因此可以同时进行，总利润为 $(9-2) + (9-1) = 15$。 在第二个示例中，尽管 Manao 可以最多进行 5 次交易，但只有 4 次交易是有利可图的。进行第五次交易会导致亏损，因此他仅进行了以下 4 次交易： ``` 2 | 7 | 3 | 9 | 8 | 7 | 9 | 7 | 1 | 9 buy | sell | buy | sell | | buy | sell | | buy | sell ``` 总利润为 $(7-2) + (9-3) + (9-7) + (9-1) = 21$。 **本翻译由 AI 自动生成**