3

这是问题：

拉穆是个懒惰的农民。他从父亲那里继承了一个相当大的农场和一所漂亮的房子。拉木将农田出租给他人，收入颇丰。他的父亲曾经在家里养一头水牛并卖掉它的牛奶，但水牛在他父亲死后几天就死了。
Ramu 也想从水牛身上赚点钱，但方式完全不同。他决定他的未来在于投机水牛。在他村里的市场上，每天都有水牛买卖。价格在一年中波动，但在任何一天，价格总是一样的。
他决定在价格低的时候买水牛，在价格高的时候卖掉它们，在这个过程中积累大量的财富。不幸的是，他的房子只能容纳一头水牛，因此他在任何时候最多只能拥有一头水牛。
在他进入水牛市场之前，他决定检查一下过去几天水牛价格的变化，并确定他可以赚取的最大利润。假设，过去 10 天一头水牛的价格变化如下：

10 12 8 11 11 10 12 15 13 10

Ramu 是一个懒惰的家伙，他估计在过去的 10 天内他最多愿意去市场 5 次（每次要么买卖一头水牛）。鉴于此，他可以赚取的最大利润是 9 卢比。为此，他在第 1 天买了一头水牛，第 2 天卖出，第 3 天再买一头，第 8 天卖出。如果他不那么懒惰，愿意去市场 6 次，那么他本可以赚更多的钱。他本可以在第 1 天买入，在第 2 天卖出，在第 3 天买入，在第 4 天卖出，在第 6 天买入并在第 8 天卖出，以赚取 10 卢比的利润。
你的任务是帮助 Ramu 计算他通过投机水牛可以赚取的最大金额，给定一段时期内每日水牛价格的历史记录以及 Ramu 在此期间愿意进入市场的次数的限制。

输入格式 输入
的第一行包含两个整数 N 和 K，其中 N 是价格数据可用的天数，K 是 Ramu 愿意访问牛市的最大次数。接下来的 N 行（第 2、3、...、N+1 行）每行都包含一个正整数。第 i+1 行的整数 1 ≤ i ≤ N，表示水牛在第 i 天的价格。

输出格式
一个单一的非负整数，表示如果 Ramu 最多 K 次进入市场，他可以赚取的最大利润。
您可以假设 N ≤ 400 和 K ≤ 400。
时间限制 = 3 秒。

如果我们没有约束 k，我们可以使用贪心方法解决这个问题，

 while c < N
   i = c
   while price[day i] > price[day i+1] increment i;
   j = i+1
   while price[day j] < price[day j+1] increment j;
   add price[day j] - price[day i] to out profit
   c = j+1

但是我们不能在这里使用它，因为是否在特定日期访问取决于我们访问了多少天。这是我尝试过的

 //Store all the pairs generated in the previous algorithm in a linked list L, each
 //element has two attributes buy,sell
 while length of L > k/2
       find an element i in the list such the (L[i].sell- L[i-1].buy) - 
       (L[i-1].buy - L[i-1].sell) - (L[i].buy - L[i].sell) is maximized.
       Then set L[i-1].sell to L[i].sell and delete i from the list

这是在线法官的一个问题，当我提交它时，我的一些测试用例超出了时间限制，一些测试用例的答案错误，只对一个测试用例进行了更正。

我的方法有什么问题，它怎么会变慢，因为它需要大约 O(NK) 时间，其中 N 和 K < 400。
如何改进我的算法以正确解决问题？

编辑：这不是家庭作业，我在这里发现了这个问题：http: //opc.iarcs.org.in/index.php/problems/BUFFALOES

4

1 回答 1

2

我没有仔细分析过，但在我看来，你对懒惰的农民的想法有点过于贪婪了。我很难想象你的链表，或者它上面的操作。

我认为考虑这个问题的一个好方法，而不用担心效率，就是把它转换成一个图表，每天都是图表中的一个节点。

如果我们有一个勤奋的交易者愿意尽可能频繁地访问市场，它看起来像下面的图 1，我在你的例子的前几天取了这个例子。图中从每一天到每一天都画出弧线，弧线的权重如下：

  • 连续的日子必须有一条弧线——要么用买入的利润加权，然后在第二天卖出，要么（如果这样的活动是亏损）加权为零
  • 如果利润为正，非连续的日子只需要弧线。（虽然您可以为非盈利货币对绘制零权重弧线，但我已将它们隐藏在下方，以便图表可读。）

该图需要 O(N^2) 比较/减法来创建。一旦有了这张图，为农民找到最佳计划就相当于通过图找到最长的路径（例如，从第一天到最后一天弧值总和最大的路径）。通常，找到通过图的最长路径是 NP-Complete，但在这种情况下，我们有一个有向无环图——您可以简单地否定所有边权重，并使用 Dijkstra 算法在多项式时间内找到最短路径。

图 1：非懒惰的农民

要对付懒惰的农民，您需要调整此图结构，使其“计算”非零弧。我们通过使图表更大来做到这一点。大了很多。如果农民愿意去市场进行 k 次旅行，他有 floor(k/2) 个买/卖对。让我们称这个数字为 X，然后每 X+1 次绘制图中的节点。

同一行中的每个连续弧（无论当天的利润如何）的权重为 0。正长度的弧被重定向到下面的行。图 2 显示了如果农民愿意去市场 4 次，总共有 2 个买入/卖出机会，情况会怎样。您还可以从每行的末尾免费添加一个虚拟“终端节点”。

您可以看到，通过确保每个获利机会从一行移动到另一行，这“计算”了利润弧，并且永远不会有机会多次使用同一行。同样，您可以找到找到正确答案的最长路径；并且该图再次是有向无环的，因此可以将其转换为最短路径问题并在多项式时间内求解。

坏消息是，节点和弧数已大大增加。如果 k=N，你可能有 O(N^2) 而不是 N 个节点。同样，不是 O(N^2) 弧，而是 O(N^3)。

图 2：懒惰的农夫

通过将问题转换为网格，您可以在时间和空间上做得更好，类似于最长公共子序列问题，但这至少说明了问题的结构。

于 2013-01-05T23:49:06.173 回答