CF391F1 Stock Trading

本题由三个子问题组成：解决子问题 F1 可获得 8 分，解决子问题 F2 可获得 15 分，解决子问题 F3 可获得 10 分。 Manao 开发了一种模型来预测未来 $n$ 天内某公司股票的价格，并希望利用这些预测设计一个交易算法来实现利润最大化。但Manao 账户在交易上有如下限制： - 同时只能持有0股或1股股票； - 每天只能买入或卖出一次股票； - 在接下来的 $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 10^9$。接下来的 $n$ 行中，每行包含一个整数 $p_i$（$0 \le p_i \le 10^{12}$），表示第 $i$ 天的股票买卖价格。 题目有三个子问题，每个子问题有不同的输入限制，正确解答每个子问题可获得不同的分数： - 子问题 F1（8 分）：$n$ 位于 $1$ 到 $3000$ 之间。 - 子问题 F2（15 分）：$n$ 位于 $1$ 到 $100000$ 之间。 - 子问题 F3（10 分）：$n$ 位于 $1$ 到 $4000000$ 之间。

程序只需输出 Manao 在未来的 $n$ 天内，按上述限制条件实现的最大利润。输出为一行一个整数，表示在第一个交易日不持有股票开始，整个交易期内最多只能持有0股或1股，并最多买入 $k$ 次的条件下可以获得的最大利润。

在第一个例子中，最佳的交易是在第 9 天以 $1$ 的价格买入，在第 10 天以 $9$ 的价格卖出；第二佳交易是在第 1 天以 $2$ 的价格买入，在第 4 天以 $9$ 的价格卖出。这两笔交易不重叠，可以同时进行，获得的总利润为两笔交易利润之和。因此，交易策略为： ``` 2 | 7 | 3 | 9 | 8 | 7 | 9 | 7 | 1 | 9 买入 | | | 卖出 | | | | | 买入 | 卖出 ``` 总利润为 $(9-2) + (9-1) = 15$。 在第二个例子中，尽管允许进行最多5笔交易，但实际上只有4笔能带来利润。进行第五笔交易会导致亏损，因此 Manao 只执行了以下4笔交易： ``` 2 | 7 | 3 | 9 | 8 | 7 | 9 | 7 | 1 | 9 买入 | 卖出 | 买入 | 卖出 | | 买入 | 卖出 | | 买入 | 卖出 ``` 总利润为 $(7-2) + (9-3) + (9-7) + (9-1) = 21$。 **本翻译由 AI 自动生成**