§ 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$ 是否合法。

转移即：

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