Link.

  给定序列 ({a_n})，问是否存在一棵二叉搜索树，使得其中序遍历为 ({a_n})，且相邻接的两点不互素。

  (nle700)。

(mathcal{Solution})

  显然的 (mathcal O(n^4)) DP：(f(l,r,i)) 表示区间 ([l,r]) 是否能构成以 (i) 为根的树。

  一个重要的性质：若区间 ([l,r]) 构成二叉搜索树的一棵完整的子树，则其父亲是 (l-1) 或 (r+1)。证明显然。

  那么状态可以优化，令 (f(l,r,0/1)) 表示区间 ([l,r]) 能否作为 (l-1/r+1) 的子树，转移：

  当 (l=1) 或 (r=n)，认为逻辑与的最后一项为真即可。复杂度 (mathcal O(n^3))。

(mathcal{Code})

#include <cstdio>

const int MAXN = 700;
int n, a[MAXN + 5];
bool f[MAXN + 5][MAXN + 5][2];

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

inline bool toLeft ( const int fid, const int id ) {
	return ! fid || ( a[fid] < a[id] && gcd ( a[fid], a[id] ) ^ 1 );
}

inline bool toRight ( const int fid, const int id ) {
	return fid > n || ( a[id] < a[fid] && gcd ( a[id], a[fid] ) ^ 1 );
}

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][0] = toLeft ( i - 1, i );
		f[i][i][1] = toRight ( i + 1, i );
		f[i][i - 1][0] = f[i][i - 1][1] = true;
	}
	f[n + 1][n][0] = f[n + 1][n][1] = true;
	for ( int len = 2; len <= n; ++ len ) {
		for ( int i = 1, j; ( j = i + len - 1 ) <= n; ++ i ) {
			bool &curl = f[i][j][0], &curr = f[i][j][1];
			for ( int k = i; k <= j && ( ! curl || ! curr ); ++ k ) {
				if ( f[i][k - 1][1] && f[k + 1][j][0] ) {
					if ( toLeft ( i - 1, k ) ) curl = true;
					if ( toRight ( j + 1, k ) ) curr = true;
				}
			}
		}
	}
	puts ( f[1][n][0] || f[1][n][1] ? "Yes" : "No" );
	return 0;
}