CF391F3.Stock Trading

This problem consists of three subproblems: for solving subproblem F1 you will receive 8 points, for solving subproblem F2 you will receive 15 points, and for solving subproblem F3 you will receive 10 points.

Manao has developed a model to predict the stock price of a company over the next n days and wants to design a profit-maximizing trading algorithm to make use of these predictions. Unfortunately, Manao's trading account has the following restrictions:

• It only allows owning either zero or one shares of stock at a time;
• It only allows buying or selling a share of this stock once per day;
• It allows a maximum of k buy orders over the next n days;

For the purposes of this problem, we define a trade to a be the act of buying one share of stock on day i, then holding the stock until some day j > i at which point the share is sold. To restate the above constraints, Manao is permitted to make at most k non-overlapping trades during the course of an n-day trading period for which Manao's model has predictions about the stock price.

Even though these restrictions limit the amount of profit Manao can make compared to what would be achievable with an unlimited number of trades or the ability to hold more than one share at a time, Manao still has the potential to make a lot of money because Manao's model perfectly predicts the daily price of the stock. For example, using this model, Manao could wait until the price is low, then buy one share and hold until the price reaches a high value, then sell for a profit, and repeat this process up to k times until n days have passed.

Nevertheless, Manao is not satisfied by having a merely good trading algorithm, and wants to develop an optimal strategy for trading subject to these constraints. Help Manao achieve this goal by writing a program that will determine when to buy and sell stock to achieve the greatest possible profit during the n-day trading period subject to the above constraints.

本题包含三个子问题：解决子问题 F1 可获得 8 分，解决子问题 F2 可获得 15 分，解决子问题 F3 可获得 10 分。

Manao 构建了一个模型，用于预测某公司股票在未来 n 天内的价格，并希望基于这些预测设计一个能最大化利润的交易算法。然而，Manao 的交易账户存在以下限制：

• 任一时刻仅允许持有零股或一股该股票；
• 每天最多只能进行一次买入操作或一次卖出操作（即每天至多执行一次买入或一次卖出，不可同时进行）；
• 在接下来的 n 天内，最多允许下达 k 笔买入订单。

在本题中，我们定义一次**交易（trade）**为：在第 i 天买入一股股票，然后持有该股票直至某个第 j 天（其中 j > i），并在该天卖出。换言之，上述约束等价于：在 Manao 拥有股票价格预测的 n 天交易周期内，Manao 最多可完成 k 次互不重叠的交易。

尽管这些限制使得 Manao 能获得的利润低于无交易次数限制或允许多股持仓的情形，但由于 Manao 的模型能完美预测每日股票价格，他仍有望获得丰厚收益。例如，借助该模型，Manao 可等待股价跌至低位时买入一股，持有至股价升至高位时卖出以获利，并重复此过程最多 k 次，直至 n 天结束。

然而，Manao 并不满足于一个“尚可”的交易算法，而是希望设计出在上述约束下的最优交易策略。请帮助 Manao 实现这一目标：编写一个程序，确定在满足上述约束的前提下，于 n 天交易周期内应于何时买入、何时卖出，从而实现最大可能利润。

The first line contains two integers n and k, separated by a single space, with . The i-th of the following n lines contains a single integer p__i (0 ≤ p__i ≤ 1012), where p__i represents the price at which someone can either buy or sell one share of stock on day i.

The problem consists of three subproblems. The subproblems have different constraints on the input. You will get some score for the correct submission of the subproblem. The description of the subproblems follows.

• In subproblem F1 (8 points), n will be between 1 and 3000, inclusive.
• In subproblem F2 (15 points), n will be between 1 and 100000, inclusive.
• In subproblem F3 (10 points), n will be between 1 and 4000000, inclusive.

第一行包含两个整数 $n$ 和 $k$，以单个空格分隔，且满足 $1 \le k \le n \le 4\cdot10^6$。接下来的 $n$ 行中，第 $i$ 行包含一个整数 $p_i$（$0 \le p_i \le 10^{12}$），其中 $p_i$ 表示在第 $i$ 天买入或卖出一股股票的价格。

本题包含三个子问题。各子问题对输入的约束条件不同。正确提交每个子问题可获得相应分数。各子问题的描述如下：

• 子问题 F1（8 分）：$n$ 的取值范围为 $1$ 到 $3000$（含端点）。
• 子问题 F2（15 分）：$n$ 的取值范围为 $1$ 到 $100000$（含端点）。
• 子问题 F3（10 分）：$n$ 的取值范围为 $1$ 到 $4000000$（含端点）。

For this problem, the program will only report the amount of the optimal profit, rather than a list of trades that can achieve this profit.

Therefore, the program should print one line containing a single integer, the maximum profit Manao can achieve over the next n days with the constraints of starting with no shares on the first day of trading, always owning either zero or one shares of stock, and buying at most k shares over the course of the n-day trading period.

对于本题，程序只需报告最优利润的数值，而无需输出达成该利润的具体交易列表。

因此，程序应输出一行，包含一个整数，即在接下来的 $n$ 天内，Manao 在以下约束条件下所能获得的最大利润：第一天交易开始时持有零股股票；任意时刻持有的股票数量只能为 0 或 1 股；在整个 $n$ 天交易期内最多买入 $k$ 股股票。

In the first example, the best trade overall is to buy at a price of 1 on day 9 and sell at a price of 9 on day 10 and the second best trade overall is to buy at a price of 2 on day 1 and sell at a price of 9 on day 4. Since these two trades do not overlap, both can be made and the profit is the sum of the profits of the two trades. Thus the trade strategy looks like this:

2 | 7 | 3 | 9 | 8 | 7 | 9 | 7 | 1 | 9
buy | | | sell | | | | | buy | sell

The total profit is then (9 - 2) + (9 - 1) = 15.

In the second example, even though Manao is allowed up to 5 trades there are only 4 profitable trades available. Making a fifth trade would cost Manao money so he only makes the following 4:

2 | 7 | 3 | 9 | 8 | 7 | 9 | 7 | 1 | 9
buy | sell | buy | sell | | buy | sell | | buy | sell

The total profit is then (7 - 2) + (9 - 3) + (9 - 7) + (9 - 1) = 21.

在第一个例子中，整体最优的交易是在第 9 天以价格 1 买入，并在第 10 天以价格 9 卖出；整体次优的交易是在第 1 天以价格 2 买入，并在第 4 天以价格 9 卖出。由于这两笔交易互不重叠，因此均可执行，总利润即为两笔交易利润之和。该交易策略如下所示：

2 | 7 | 3 | 9 | 8 | 7 | 9 | 7 | 1 | 9
buy | | | sell | | | | | buy | sell

总利润为 $(9 - 2) + (9 - 1) = 15$。

在第二个例子中，尽管 Manao 最多可进行 5 笔交易，但其中仅有 4 笔是盈利的。若强行进行第 5 笔交易将导致亏损，因此 Manao 仅执行以下 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$。