Codeforces 1025D Recovering BST

题面在这里

题意：给一个序列，问是否能构成这样的二叉搜索树，满足相邻节点gcd大于1

​

区间DP……

考虑一个区间代表一棵子树，那么区间\([l,r]\)的父亲一定是\(l-1\)或\(r+1\)

\(f_{l,r,0/1}\)表示区间\([l,r]\)，这棵树是左子树还是右子树

枚举一个根，转移即可

​

示例程序：

#include<cstdio>
#include<cstring>

const int maxn=705;
int n,a[maxn],f[maxn][maxn][2];
bool cst[maxn][maxn];
int gcd(int x,int y) {return !y?x:gcd(y,x%y);}
bool dfs(int l,int r,int d){
	if (l>r) return 1;
	if (f[l][r][d]>=0) return f[l][r][d];
	int fa=(d?r+1:l-1);
	for (int i=l;i<=r;i++)
	 if (cst[fa][i]&&dfs(l,i-1,1)&&dfs(i+1,r,0)) return f[l][r][d]=1;
	return f[l][r][d]=0;
}
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]),cst[i][0]=cst[0][i]=1;
	for (int i=1;i<=n;i++)
	 for (int j=1;j<=n;j++) cst[i][j]=(gcd(a[i],a[j])>1);
	memset(f,-1,sizeof(f));
	if (dfs(1,n,0)) puts("Yes");else puts("No");
	return 0;
}