c - 我如何以更快更准确的方式解决这个问题？

Question

问题是:

Ramu was a lazy farmer. He had inherited a fairly large farm and a nice house from his father. Ramu leased out the farm land to others and earned a rather handsome income. His father used to keep a buffalo at home and sell its milk but the buffalo died a few days after his father did.
Ramu too wanted to make some money from buffaloes, but in a quite a different way. He decided that his future lay in speculating on buffaloes. In the market in his village, buffaloes were bought and sold everyday. The price fluctuated over the year, but on any single day the price was always the same.
He decided that he would buy buffaloes when the price was low and sell them when the price was high and, in the process, accummulate great wealth. Unfortunately his house had space for just one buffalo and so he could own at most one buffalo at any time.
Before he entered the buffalo market, he decided to examine to examine the variation in the price of buffaloes over the last few days and determine the maximum profit he could have made. Suppose, the price of a buffalo over the last 10 days varied as

10 12 8 11 11 10 12 15 13 10

Ramu is a lazy fellow and he reckoned that he would have been willing to visit the market at most 5 times (each time to either buy or sell a buffalo) over the last 10 days. Given this, the maximum profit he could have made is 9 rupees. To achieve this, he buys a buffalo on day 1, sells it on day 2, buys one more on day 3 and sells it on day 8. If he was a little less lazy and was willing to visit the market 6 times, then he could have made more money. He could have bought on day 1, sold on day 2, bought on day 3, sold on day 4, bought on day 6 and sold on day 8 to make a profit of 10 rupees.
Your task is help Ramu calculate the maximum amount he can earn by speculating on buffaloes, given a history of daily buffalo prices over a period and a limit on how many times Ramu is willing to go to the market during this period.

Input format
The first line of the input contains two integers N and K, where N is the number of days for which the price data is available and K is the maximum number of times that Ramu is willing to visit the cattle market. The next N lines (line 2, 3,...,N+1) contain a single positive integer each. The integer on line i+1, 1 ≤ i ≤ N, indicates the price of a buffalo on day i.

Output format
A single nonnegative integer indicating that maximum amount of profit that Ramu can make if he were to make at most K trips to the market.
You may assume that N ≤ 400 and K ≤ 400.
Time limit = 3sec.

如果我们没有约束 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

Answer 1

我没有仔 segmentation 析过，但在我看来，你对懒农的想法有点太贪婪了。我很难想象您的链表或链表上的操作。

我认为在不担心效率的情况下考虑这个问题的一个好方法是将其转换为图表，其中每一天都是图表中的一个节点。

如果我们有一个勤奋的交易者愿意尽可能经常地访问市场，它看起来像下面的图 1，我在你的例子的前几天。图中从每天到以后的每一天绘制弧线，弧线的权重如下:

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

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

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

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

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

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

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