可排列的最长链条

Question

我在比赛的某个地方发现了这个问题，但还没能想出解决办法。

I have the positive integers. I have to find longest subset that among each two neighbour elements one divides another.

我正在做的是：我正在创建 graph.Then 我正在连接节点，在这些节点中数字彼此分开。之后我使用DFS（一个节点可以连接两个节点）。

但并不是所有的测试用例在系统中都是正确的。使用 DFS 之前是否必须对数组进行排序？也许有特殊的（动态）算法？

失败的测试用例：

N = 5
1 1 3 7 13

我的代码给出了输出 4。但是如果我 arrange 这个数组是这样的：

3 1 7 1 13

输出为 5，这是正确的答案。

我也是用递归的方法。但我需要更快的东西。

Answer 1

您忘记重新初始化一些变量：used 和 kol。此外，DFS 不会在下一次调用结束时恢复 used[i]。

尽量避免使用全局变量，这样会使代码不那么清晰。也尝试缩小变量的范围。

代码可能类似于：

void DFS(int (&used)[20], const int (&m)[20][20], int c, int& maxn, int k, int v) {
    used[v] = 1;
    k += 1;
    if(k > maxn)
        maxn = k;
    for(int i = 0; i < c; ++i) {
        if(!used[i] && m[v][i] == 1) {
            DFS(used, m, c, maxn, k, i);
        }
    }
    used[v] = 0;
}

主要是：

int m[20][20];
memset(m, 0, sizeof(m));

for(int i = 0; i < c; ++i) {
    for(int j = i + 1; j < c; ++j) {
        if( (a[i] % a[j] == 0) || (a[j] % a[i] == 0) ) {
            m[i][j] = m[j][i] = 1; // Creating 2D array
        }
    }
}

int maxn = 0;
for(int i = 0; i < c; ++i) {
    int used[20];
    int k = 0;
    memset(used, 0, sizeof(used));
    DFS(used, m, c, maxn, k, i);
}
std::cout << maxn << std::endl;

Live Demo

代码可以进一步简化（使用 vector, ...）

Answer 2

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

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

例如，如果我们有一个图

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

然后我们可以标记

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-hard，所以 nhahtdh 关于 O(2^n poly(n)) 时间动态程序的评论是正确的——参见这个问题和接受的答案：.

可排列的最长链条

Longest chain that can be arranged

c++

algorithm

graph-theory

depth-first-search