动态规划/子问题转换

Question

我有点卡住了，我决定试试这个问题https://icpcarchive.ecs.baylor.edu/external/71/7113.pdf

为了防止它404'ing这里是基本的任务

a hopper only visits arrays with integer entries,
• a hopper always explores a sequence of array elements using the following rules:
– a hopper cannot jump too far, that is, the next element is always at most D indices away
(how far a hopper can jump depends on the length of its legs),
– a hopper doesn't like big changes in values — the next element differs from the current
element by at most M, more precisely the absolute value of the difference is at most M (how
big a change in values a hopper can handle depends on the length of its arms), and
– a hopper never visits the same element twice.
• a hopper will explore the array with the longest exploration sequence.


n is the length of the array (as described above, D is the maximum length of a jump the
hopper can make, and M is the maximum difference in values a hopper can handle). The next line
contains n integers — the entries of the array. We have 1 ≤ D ≤ 7, 1 ≤ M ≤ 10, 000, 1 ≤ n ≤ 10, 000
and the integers in the array are between -1,000,000 and 1,000,000.

编辑：我这么做纯粹是出于好奇。除了挑战自己，我不需要出于任何特殊原因去做这项任务

基本上，它是从一个数组中构建一个稀疏图，该图是无向的，并且由于-d的对称性。。。d跳跃，它也可以是一个完整的图（包括所有边）或相互不相交的图组件

作为第一步，我尝试简单地详尽地DFS搜索图，它可以工作，但具有臭名昭著的O（n！）运行时，第一次迭代是用F#编写的，速度非常慢，第二次用C编写，速度仍然非常快，所以我知道最长的路径问题是NP难，但我想我会尝试使用动态编程

下一种方法是简单地使用通用DP解决方案（bitmask path）来在图上进行DFS，但在这一点上，我已经遍历了数组并构建了可能包含多达1000个节点的整个图，因此它是不可行的

我的下一个方法是构建一个DFS树（所有路径的树），它的速度要快一点，但是每次迭代都需要将所有路径存储在内存中，这不是我真正想要的，我想我可以在遍历数组的同时将其缩减为子状态

接下来，我尝试通过使用位掩码和简单的记忆功能来记忆我已经走过的所有路径，如下所示：

let xf = memoizedEdges (fun r i' p mask  -> 
                    let mask' = (addBit i' mask)
                    let nbs =  [-d .. -1] @ [ 1 .. d] 
                                |> Seq.map (fun f -> match f with 
                                                        | x when (i' + x) < 0 -> None
                                                        | x when (i' + x) >= a.Length -> None
                                                        | x when (diff a.[i'+x] a.[i']) > m -> None
                                                        | x when (i' + x) = i -> None 
                                                        | x when (isSet (i'+x) mask') -> None
                                                        | x -> Some (i' + x )
                                                        ) 
                    let ec = nbs 
                                |> Seq.choose id 
                                |> Seq.toList
                                |> List.map (fun  f  ->
                                                r f i' mask'
                                ) 
                    max  (bitcount mask) (ec |> mxOrZero)
                )

因此，记忆边通过3个int参数工作——当前索引（i’）、前一个（p）和作为位掩码的路径，momizedEdges函数本身将在每次递归调用时检查它是否看到i’和p以及掩码。。。或者p和i'以及带有i'和p位的掩码翻转，以另一种方式屏蔽路径（基本上如果我们已经看到这条路径来自另一侧）

这与我预期的一样工作，但赋值状态为最多1000个索引，这将导致int32掩码太短

所以我已经想了好几天了，必须有一种方法来编码每个-d。。。d步进起点和终点，并根据前面的步骤计算该窗口中每个步骤的路径

我基本上想到了这个

  0.) Create a container to hold starting and endvertex as key with the current pathlength as value
  1.) Check neighbors of i
  2.) Have I seen either this combination either as (from -> to) or (to -> from) then I do not add or increase
  3.) Check whatever any other predecessors to this node exist and increase the path of those by 1
  

但这将导致存储所有路径，我基本上会导致元组，然后我以另一种形式回到我的DFS图

我非常感谢大家给我的建议（我只是需要一些新的想法，我真的被卡住了），告诉我如何从-d对每个子问题进行编码。。d我可以使用中间结果来计算下一步（如果可能的话）




Answer 1

这是一个难题。事实上，在竞争性编程问题纲要卡蒂斯上，它（在撰写本文时）是最困难的问题的前5名。

只有你知道这种问题是否有可能为你解决，但有一个公平的机会，没有人在这个网站上可以完全帮助你，因此这个部分答案。

这里要求我们做的是解决特定图的最长路径问题。众所周知，这个问题通常是NP完全的，即使对于像我们这样的无向未加权图也是如此。因为图可以有1000个顶点，所以N中的（子）指数算法是行不通的，而且我们可能不需要证明P=NP，所以我们剩下的唯一选择就是以某种方式利用图的结构。

最有希望的途径是通过D。D最多为7，因为图的最大度最多为14，并且所有的边在某种意义上都是局部的。

现在，根据维基百科的说法，最长路径问题可以在各种类型的图上多项式求解，比如非循环图。我们的图当然不是非循环的，但不幸的是，这在很大程度上是我知识的终点。我对图论还不够熟悉，不知道维基百科提到的任何一个类中是否有这个问题的隐含图。

特别值得注意的是，给定有界的常数团宽度（或树宽度，这意味着前者），最长路径问题可以在多项式时间内解决。由于D上的界，我无法确认或证明我们的图有界团宽度，但也许你自己对此了解得更多，或者你可以尝试在math或CS stackexchange上提问，因为在这一点上，我们与任何实际编程都相去甚远。

不管怎样，如果你能确认这个图是集团宽度有界的，这篇文章可能会帮助你进一步。

我希望这个答案是有用的，尽管不是完全满足，祝你好运！

Fomin，F.V.，Golovach，P.A.，Lokshtanov，D。，