← 返回题目列表

Codeforces · 391/F3

F3. 股票交易

中文机器翻译题面 查看原题

该问题由三个子问题组成:解决子问题 F1,您将获得 8 分,解决子问题 F2,您将获得 15 分,解决子问题 F3,您将获得 10 分。

Manao 开发了一个模型来预测一家公司未来 n 天内的股价,并希望设计一个利润最大化的交易算法来利用这些预测。不幸的是,Manao的交易账户有以下限制:

- 一次只允许拥有零股或一股股票;
- 每天只允许买卖该股票一次;
- 在接下来的 n 天内最多允许 k 个买入订单;

就该问题而言,我们将交易定义为在第 i 天购买一股股票,然后持有该股票直到某一天 j > i,此时出售该股票的行为。为了重申上述限制,在 Manao 模型预测股价的 n 天交易期内,Manao 最多可以进行 k 笔非重叠交易。

尽管这些限制限制了 Manao 可以赚取的利润,但与无限数量的交易或一次持有多股的能力相比,Manao 仍然有可能赚很多钱,因为 Manao 的模型完美地预测了股票的每日价格。例如,使用此模型,Manao 可以等到价格较低,然后购买一股并持有,直到价格达到较高值,然后出售以获取利润,并重复此过程最多 k 次,直到 n 天过去。

尽管如此,Manao 并不满足于仅仅拥有良好的交易算法,而是希望开发一种受这些约束的最佳交易策略。通过编写一个程序来帮助马瑙实现这一目标,该程序将确定何时买卖股票,以在受到上述约束的 n 天交易期间内实现最大可能的利润。

输入

第一行包含两个整数 n 和 k,用一个空格分隔,其中 $$1 \leq k \leq \frac{n}{2}$$。以下 n 行中的第 i 行包含一个整数 pi (0 ≤ pi ≤ 1012),其中 pi 表示某人在第 i 天可以买入或卖出一股股票的价格。

该问题由三个子问题组成。子问题对输入有不同的约束。正确提交子问题将获得一些分数。子问题的描述如下。

- 在子问题 F1(8 点)中,n 将介于 1 和 3000 之间(包含 1 和 3000)。
- 在子问题 F2(15 点)中,n 将介于 1 和 100000 之间(包含 1 和 100000)。
- 在子问题 F3(10 分)中,n 将介于 1 和 4000000 之间(含)。

输出

对于这个问题,程序只会报告最优利润的金额,而不是可以实现该利润的交易列表。

因此,程序应该打印一行包含一个整数,Manao 在接下来的 n 天内可以实现的最大利润,限制条件是从第一天交易开始时没有股票,始终拥有 0 股或 1 股股票,并且在 n 天的交易期间最多购买 k 股。

示例

输入 #1

10 2
2
7
3
9
8
7
9
7
1
9

输出 #1

15

输入 #2

10 5
2
7
3
9
8
7
9
7
1
9

输出 #2

21

注意

在第一个示例中,总体最佳交易是在第 9 天以 1 的价格买入并在第 10 天以 9 的价格卖出,总体第二最佳交易是在第 1 天以 2 的价格买入并在第 4 天以 9 的价格卖出。由于这两个交易不重叠,因此两者都可以进行,利润是两个交易利润的总和。因此,交易策略如下所示:

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

在第二个示例中,尽管允许 Manao 进行最多 5 笔交易,但只有 4 笔有利可图的交易可用。进行第五次交易会花费 Manao 钱,因此他只进行以下 4 次交易:

总利润为 (7 - 2) + (9 - 3) + (9 - 7) + (9 - 1) = 21。