最长的链条可以安排

Question

我在比赛的某个地方发现了这个问题,但还没有找到解决方案.

我有正整数.我必须找到最长的子集,在每两个相邻元素中,一个除以另一个.

我正在做的是:我正在创建图形.然后我正在连接其中数字彼此分开的节点.之后我正在使用DFS(一个节点可以连接两个节点).

但并非所有测试用例都适用于系统.在使用之前我是否必须对数组进行排序DFS？也许有特殊的(动态)算法？

失败的测试用例:

N = 5
1 1 3 7 13

我的代码给出了输出4.但如果我arrange这个数组像这样:

3 1 7 1 13

输出是5,这是真正的答案.

我也使用了递归方法.但我需要更快的东西.

Answer 1

这是最长的路径，稍微伪装了一下。我们可以通过准备一个图来解决这个最长路径问题，其中两个顶点相邻当且仅当它们满足整除关系时。请参阅下面的水平规则以获取指向预期答案的指针。

简化是（粗略地）给定一个无向图，我们希望在其中找到最长的简单路径，为每个顶点分配一个不同的素数。对于每条边，发出这些素数以及作为其端点乘积的半素数。（我们还需要另外两个素数及其与顶点素数的 2|V| 乘积，以附加地保留目标。）

例如，如果我们有一个图

*---*
|  /|
| / |
|/  |
*---*,

然后我们可以标记

2---3
|  /|
| / |
|/  |
5---7,

然后输入是

2, 3, 5, 7,  # vertices
2*3, 2*5, 3*5, 3*7, 5*7,  # edges
11*2, 11*3, 11*5, 11*7,  # sentinels at one end
2*13, 3*13, 5*13, 7*13,  # sentinels at the other end

（例如）最长路径2, 3, 5, 7对应于最长序列11*2, 2, 2*3, 3, 3*5, 5, 5*7, 7, 7*13（以及涉及反转和交换的其他三个变体11和13）。

最长的路径是 NP 难的，所以 nhahtdh 关于 O(2^n poly(n)) 时间动态程序的评论是正确的——请参阅这个问题和接受的答案：Longest path in unweighted undirected graph。