c++ - 可排列的最长链条

Question

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

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

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

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

失败的测试用例:

N = 5
1 1 3 7 13

我的代码给出了输出 4。但是如果我像这样安排这个数组:

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, ...)