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;
}