Link

Sol

注意到这是一个二叉树，而且是一棵二叉排序树

一棵二叉树，也就是说对于一个点它只有左右两个儿子。我们可以在一个区间内dp来选择它的左右儿子。我们设$f[i][j][k]$表示在区间$[i,j]$内以是否能以$k$为根并且满足任意两个直接相连的点之间的权值最大公约数不是$1$的条件。$O(n^2)$ 地枚举区间，$O(n)$ 地枚举根，$O(n)$ 地枚举儿子节点。时间复杂度为 $O(n ^4)$

因为这是一棵BST，它的中序遍历的话权值就是从小到大的。构造合法的树也会满足这样的条件。也就是说，区间$[i,j]$组成子树的父节点一定是$i-1$或$j+1$

设$opt[i][j]$表示$a[i]$和$a[j]$的公因数是否不为1。设$f[i][j][0/1]$ 表示区间$[i,j]$以$0: i-1$ 或 $1: j +1$ 为父节点时是否可行。若该区间本身可行，当前枚举的根为$k$， 若$opt[i-1][k] = 1$ ，则$f[i][k][0] = 1$。 以$j+1$为父节点的情况同理

这样以来省去一维状态，时间复杂度降至$O(n^3)$，可以通过本题。具体实现的时候可以预处理两个数的最大公因数是否为$1$来转移。当区间$[1,n]$出现一种合法状态的时候，即可输出Yes，否则无解。

Code

#include <bits/stdc++.h>
using namespace std;

const int SIZE = 7e2 + 5;

int n;
int a[SIZE], opt[SIZE][SIZE], f[SIZE][SIZE][2];

namespace ae86 {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (!isdigit(c))b ^= c == '-', c = fetch();
        while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
        return b ? a : -a;
    }
}
using ae86::read;

int gcd(int a, int b) {
    return !b ? a : gcd(b, a % b);
}

int main() {
    // freopen("code.in", "r", stdin);
    n = read();
    for (int i = 1; i <= n; ++ i) a[i] = read(), f[i][i][0] = f[i][i][1] = 1;
    for (int i = 1; i <= n; ++ i) {
        for (int j = i + 1; j <= n; ++ j) {
            if (gcd(a[i], a[j]) != 1) opt[i][j] = opt[j][i] = 1;
        }
    }
    for (int len = 1; len <= n; ++ len) {
        for (int i = 1, j; i + len - 1 <= n; ++ i) {
            j = i + len - 1;
            for (int k = i; k <= j; ++ k) {
                if (f[i][k][0] && f[k][j][1]) {
                    if (i == 1 && j == n) { puts("Yes"); return 0; }
                    if (opt[i - 1][k]) f[i - 1][j][1] = 1;
                    if (opt[k][j + 1]) f[i][j + 1][0] = 1;
                }
            }
        }
    }
    puts("No");
    return 0;
}