动态规划/子问题+转换
Dynamic Programming / Subproblems + Transition
我有点卡住了，我决定试试这个问题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 解决方案（位掩码路径）在图上进行 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)
)
所以 memoized edges 通过 3 个 int 参数工作，当前索引 (i')，前一个 (p) 和作为位掩码的路径，momizedEdges 函数本身将检查每个递归调用它是否已经看到 i' 和 p和掩码...或 p 和 i' 以及带有 i' 和 p 位的掩码翻转以以另一种方式掩码路径（基本上如果我们已经看到这条路径来自另一侧）
这正如我所期望的那样工作，但是赋值说明它最多有 1000 个索引，这会导致 int32 掩码太短
所以我已经思考了好几天了，必须有一种方法可以将每个 -d ... d 步骤编码为开始和结束顶点，并计算其中每个步骤的路径 window 基于前面的步骤
我基本上想到了这个
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 返回我的图表
我非常感谢任何指点（我只需要一些新想法，我真的被卡住了 rn）如何从 -d..d 编码每个 subproblem，我可以只使用中间结果来计算下一步（如果可能的话）
部分回答
这是一道难题。事实上，在竞争性编程问题纲要中 Kattis 它（在撰写本文时）是最困难问题的前 5 名。
只有您自己知道这类问题是否有可能由您解决，但很有可能此站点上没有人可以完全帮助您，因此只给出部分答案。
最长路径
我们在这里要做的是解决特定图的最长路径问题。众所周知，这个问题通常是 NP 完全问题，即使对于像我们这样的无向未加权图也是如此。因为图可以有 1000 个顶点，N 中的（子）指数算法将不起作用，我们可能不会被要求证明 P=NP，所以我们剩下的唯一选择就是以某种方式利用图的结构。
最有希望的途径是通过D。D最多为7，因此图的最大度最多为14，并且所有边在某种意义上都是局部的。
现在，根据Wikipedia，最长路径问题可以在各种类 图上用多项式求解，例如非循环图。我们的图当然不是非循环的，但不幸的是，我的知识主要到此为止。我对图论不够熟悉，看不出问题的隐含图是否在 类 维基百科提及的任何内容中。
需要特别注意的是，最长路径问题可以在多项式时间内解决，给定一个恒定的集团宽度（或树宽度，这意味着前者）。由于 D 上的界限，我无法确认或证明我们的图具有有限的 clique-width，但也许你自己对此了解更多，或者你可以尝试在数学或 CS stackexchange 上询问，因为此时我们与任何实际编程相去甚远。
无论如何，如果您能够确认图形是有界宽度的，this paper 可能会进一步帮助您。
我希望这个答案有一些用处，尽管并不完全令人满意，祝你好运！
在 link 衰变的情况下对论文的引用
Fomin, F. V.、Golovach, P. A.、Lokshtanov, D. 和 Saurabh, S.（2009 年 1 月）。 Clique-width：以通用性为代价。 第 20 届年度 ACM-SIAM 离散算法研讨会论文集（第 825-834 页）。工业与应用数学学会。
我有点卡住了，我决定试试这个问题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 解决方案（位掩码路径）在图上进行 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)
)
所以 memoized edges 通过 3 个 int 参数工作，当前索引 (i')，前一个 (p) 和作为位掩码的路径，momizedEdges 函数本身将检查每个递归调用它是否已经看到 i' 和 p和掩码...或 p 和 i' 以及带有 i' 和 p 位的掩码翻转以以另一种方式掩码路径（基本上如果我们已经看到这条路径来自另一侧）
这正如我所期望的那样工作，但是赋值说明它最多有 1000 个索引，这会导致 int32 掩码太短
所以我已经思考了好几天了，必须有一种方法可以将每个 -d ... d 步骤编码为开始和结束顶点，并计算其中每个步骤的路径 window 基于前面的步骤
我基本上想到了这个
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 返回我的图表
我非常感谢任何指点（我只需要一些新想法，我真的被卡住了 rn）如何从 -d..d 编码每个 subproblem，我可以只使用中间结果来计算下一步（如果可能的话）
部分回答
这是一道难题。事实上，在竞争性编程问题纲要中 Kattis 它（在撰写本文时）是最困难问题的前 5 名。
只有您自己知道这类问题是否有可能由您解决，但很有可能此站点上没有人可以完全帮助您，因此只给出部分答案。
最长路径
我们在这里要做的是解决特定图的最长路径问题。众所周知，这个问题通常是 NP 完全问题，即使对于像我们这样的无向未加权图也是如此。因为图可以有 1000 个顶点，N 中的（子）指数算法将不起作用，我们可能不会被要求证明 P=NP，所以我们剩下的唯一选择就是以某种方式利用图的结构。
最有希望的途径是通过D。D最多为7，因此图的最大度最多为14，并且所有边在某种意义上都是局部的。
现在，根据Wikipedia，最长路径问题可以在各种类 图上用多项式求解，例如非循环图。我们的图当然不是非循环的，但不幸的是，我的知识主要到此为止。我对图论不够熟悉，看不出问题的隐含图是否在 类 维基百科提及的任何内容中。
需要特别注意的是，最长路径问题可以在多项式时间内解决，给定一个恒定的集团宽度（或树宽度，这意味着前者）。由于 D 上的界限，我无法确认或证明我们的图具有有限的 clique-width，但也许你自己对此了解更多，或者你可以尝试在数学或 CS stackexchange 上询问，因为此时我们与任何实际编程相去甚远。
无论如何，如果您能够确认图形是有界宽度的，this paper 可能会进一步帮助您。
我希望这个答案有一些用处，尽管并不完全令人满意，祝你好运！
在 link 衰变的情况下对论文的引用
Fomin, F. V.、Golovach, P. A.、Lokshtanov, D. 和 Saurabh, S.（2009 年 1 月）。 Clique-width：以通用性为代价。 第 20 届年度 ACM-SIAM 离散算法研讨会论文集（第 825-834 页）。工业与应用数学学会。