下面的问题：

瑞木是一个懒散的农民。他继承了一个相当大的农场和一间漂亮的房子，从他的父亲。瑞木出租农场土地给他人，并赢得了一个相当帅气的收入。他的父亲以前把水牛在家里，出售牛奶，但水牛去世后，他的父亲做了几天。   拉姆也想挣点钱从水牛，但在一个完全不同的方式。他决定他的未来在猜测水牛躺在。在市场上在他的村庄，水牛被收购和日常销售。价格波动超过一年，但在任何一天价格却总是相同的。   他决定，他会买老牛当时的价格低，出售时的价格较高，并在这个过程中，accummulate巨大的财富。不幸的是他的房子有空间，只有一个水牛，所以他可以拥有最多一个水牛在任何时间。   在他进入水牛市场，他决定审查，审查水牛在过去几天的价格变化，并确定他能取得最大的利润。假设，水牛的价格在过去的10天不等的

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

10 12 8 11 11 10 12 15 13 10

瑞木是一个懒惰的家伙，他估摸，他会一直愿意（每次购买或出售水牛）在过去的10天走访市场最多5次。鉴于此，他可能做了最大的利润是9卢比。为了实现这一目标，他买一头水牛在第1天，第2天卖了，买多了一个3天，卖了第8天。如果他不那么懒，愿意走访市场6次，然后他可以作出更多的钱。他本来可以买了第1天，第2天卖了，买了第3天，第4天卖了，买了6天，第8天出售赚取利润的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.

输入格式   输入的第一行包括两个整数N和K，其中N是天的量，价格数据可用，并且K是次的最大数目拉姆愿意访问牛市场的数目。接下来的N行（行2，3，...，N + 1）包含一个正整数的每个。上线的整数i + 1，1≤I≤N，表示水牛的价格在第一天我。

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.

输出格式   一个单一的非负整数，表明利润最高金额的瑞木可以，如果他做出最多有K游市场。   你可以假设N≤400和K≤400   时限= 3秒。

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，我们可以用一个贪婪的方法解决这个问题，

If we did not have the constraint k, we could solve this problem using a greedy approach,

 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

但是，我们不能在这里使用它，因为无论是在一个特定的时间去拜访与否取决于我们有多少天访问的。 以下是我曾试图

But we cant use it here because whether to visit on a particular day or not depends on how many days we visited. Here is what i had tried

 //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

这是一个在线的法官一个问题，当我提出它，我得到了超过时限一些测试用例和错误答案的一些正确的只是一个测试用例。

This is a problem on an online judge and when i submitted it I got time limit exceeded for some of the test cases and wrong answer for some and correct for just one test case.

什么是错误的，我的方法，以及它如何可能会很慢，因为它需要大约O（NK）的时间，其中N和K＆LT; 400. 我怎样才能提高我的算法正确地解决这个问题呢？

What is wrong in my method, and how can it be slow because it takes about O(NK) time where N and K < 400. How can i improve my algorithm to solve the problem correctly?

编辑：这不是功课，我发现这个问题就在这里： HTTP：/ /opc.iarcs.org.in/index.php/problems/BUFFALOES

This is not homework, i found this problem here: http://opc.iarcs.org.in/index.php/problems/BUFFALOES

推荐答案

我还没有分析它密切，但在我看来，你的想法懒惰的农夫有点过于贪婪。我有一个很难可视化的链接列表，或在其上的操作。

I haven't analyzed it closely, but it seems to me your idea for the lazy farmer is a little too greedy. I am having a hard time visualizing your linked list, or the operations on it.

我想一个好办法，想想这一点，而不必担心效率，就是施放此成图，其中每一天是图中的一个节点。

I think a good way to think about this, without worrying about efficiency, is to cast this into a graph, where each day is a node in the graph.

如果我们有一个勤劳的交易者愿意逛市场，尽可能多，它看起来像图1所示，在这里我已经拍了你的榜样的最初几天。弧从每天每绘制的购买的天在图中，与弧加权如下：

If we have an industrious trader willing to visit the market as often as possible, it looks like Figure 1 below, where I've taken the first few days of your example. Arcs are drawn from every day to every later day in the graph, and the arcs are weighted as follows:

在连续多日的必须的有arc--要么加权买盘的利润，然后卖的第二天，或者（如果这样的活动将是一个损失）加权零 非连续两天只需要一个弧形如果利润为正。 （虽然你可以画在零重量弧为非营利对，我有SUP pressed他们下面，这样的图形是可读的。） Consecutive days must have an arc-- either weighted with the profit of buying and then selling on the next day, or (if such an activity would be a loss) weighted zero Non-consecutive days only need an arc if the profit is positive. (Although you could draw in the zero-weight arcs for non-profitable pairs, I have suppressed them below so that the graph is readable.)

此图需要O（N ^ 2）比较/减法打造。一旦有了这种图，找到最佳的计划为农民相当于寻找最长路径（例如，从第一天到与圆弧值的总和最大的最后一天的路径）通过图形。一般，寻找通过图形的最长路径是NP完全，但在这种情况下，我们有一个向无环graph--可以简单地否定所有的边缘的权重，并找到与Dijkstra算法在多项式时间的最短路径。

This graph takes O(N^2) comparison/subtractions to create. Once you have this graph, finding the best plan for the farmer is equivalent to finding the longest path (e.g., the path from the first day to the last day with the largest sum of arc values) through the graph. Usually, finding the longest path through the graph is NP-Complete, but in this case, we have a directed acyclic graph-- you can simply negate all the edge weights and find the shortest path with Dijkstra's algorithm in polynomial time.

要对付懒惰的农夫，你需要以这样的方式适应这种图形结构，它罪状非零弧。为此，我们通过图更大。大了很多。如果农民愿意作出ķ前往市场，他有楼（K / 2）买入/卖出对。让我们把这个数字X，并绘制了曲线图的节点，每个节点X + 1次。

To deal with a lazy farmer, you need to adapt this graph structure in such a way that it "counts" the non-zero arcs. We do this by making the graph bigger. A lot bigger. If the farmer is willing to make k trips to the market, he has floor(k/2) buy/sell pairs. Let's call that number X, and draw the nodes of our graph each X+1 times.

每个连续弧同一行中（不管利润当天）具有0的重正长度的弧重定向到下面的行。图2显示了这个样子，如果农民愿意作出4趟市场，2总买入/卖出的机会。还可以添加一个虚拟的终端节点，你可以从每行的最后搞定，不花钱。

Each consecutive arc in the same row (regardless of profit for that day) has a weight of 0. The arcs of positive length are redirected to the row below. Figure 2 shows what this looks like if the farmer is willing to make 4 trips to the market, for 2 total buy/sell opportunities. You also add a dummy "terminal node" that you can get to from the end of each row, at no cost.

您可以看到，这个罪名利润弧线，确保每个机会获利就会从行与行，而且从未有机会使用同一行多次。如此反复，你可以找到找到正确的答案最长的路径;并再次，图形是向无环所以这可以被转换为一个最短路径问题和在多项式时间解决。

You can see that this "counts" the profit arcs by ensuring that each opportunity to profit moves from row to row, and there is never an opportunity to use the same row more than once. So again, you can find the longest path to find the right answer; and again the graph is directed acyclic so this can be converted to a shortest path problem and solved in polynomial time.

坏消息是，节点和弧数量已经大幅度上升。而是N个节点中，你有可能O（N ^ 2）如果k = N。同样地，而不是O（N ^ 2）弧，你有O（N ^ 3）。

The bad news is, the node and arc count have gone up considerably. Instead of N nodes, you have potentially O(N^2) if k=N. Likewise, instead of O(N^2) arcs, you have O(N^3).

您可以通过铸造的问题，因为一个网格，类似最长公共子序列的问题做了时间和空间的更好，但是这至少说明了问题的结构。

You may be able to do a better in both time and space by casting the problem as a grid, similar to the longest common subsequence problem, but this at least illustrates the structure of the problem.