Description
Link.
给定一个升序序列，问是否存在一种方法使得这个升序序列构成一棵 BST 并使一边相连的两点点权互质。
Solution
根据 BST 的性质可知对于一棵以 $u$ 为根的子树 $\text{subtree}(u)$ 对应原序列中的一段区间，于是对于一个区间 $[l,r]$，如果我们选取 $k$ 作为根，那么 $\text{subtree}(u)$ 的形态就固定下来了。
设 $f(i,j,k)$ 为区间 $[i,j]$ 中以 $k$ 为根是否能够构成一棵 BST。
这不好，这很差，考虑怎么优化。
观察发现 $[l,r]$ 的父亲结点一定是 $l-1$ 或 $r+1$，于是重新设 $f(i,j,0\text{ or }1)$ 表示区间 $[i,j-1]$ 的父结点为 $j$ 是否合法 / 区间 $[i+1,j]$ 的父结点为 $i$ 是否合法。
转移即：
$$ f(i-1,j,1)=f(i-1,j,1)\vee f(i,k,0)\wedge f(k,j,1)\wedge(\gcd(a_{i-1},a_{k})\neq1) \\ f(i,j+1,0)=f(i,j+1,0)\vee f(i,k,0)\wedge f(k,j,1)\wedge(\gcd(a_{j+1},a_{k})\neq1) $$
$k$ 是区间 DP 的中间点。于是就可以做了，边界与答案显然。
#include<bits/stdc++.h>
#define f(i,j,k) (f[i][j][k])
int n,a[710];
bool f[710][710][2],flag[710][710];
int GCD(int one,int ano)
{
if(ano==0) return one;
else return GCD(ano,one%ano);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=1;i<=n;++i) f(i,i,1)=f(i,i,0)=1;
for(int i=1;i<=n;++i)
{
flag[i][0]=1;
for(int j=i;j<=n;++j)
{
flag[i][j]=flag[j][i]=(GCD(a[i],a[j])!=1);
flag[0][j]=1;
}
}
for(int i=n;i;--i)
{
for(int j=i;j<=n;++j)
{
for(int k=i;k<=j;++k)
{
f(i-1,j,1)|=(f(i,k,0)&f(k,j,1)&flag[i-1][k]);
f(i,j+1,0)|=(f(i,k,0)&f(k,j,1)&flag[j+1][k]);
}
}
}
printf((f(1,n,0)|f(1,n,1))?"Yes\n":"No\n");
return 0;
}