感觉很妙,所以来水题解了~

问给你一个升序序列,问是不是可以还原一个bstbst,使得相邻的两个节点gcdgcd不为11.n<=700n<=700.

因为是颗二叉树,很容易想到区间dpdp,然后假设区间[l,k][l,k]满足了,这个区间的父亲节点要么是l1l-1,要么是k+1k+1.可以假设它的父亲节点是l2/k+2l-2/k+2,可以发现无法构造这颗树.这就是一个很好的性质,这样我们就可以进行区间dpdp了.

一个显然的结论假如区间[l,k][l,k][k+1,r][k+1,r]都已经安排妥当,那么能否将它们合并呢?

不妨令dpdp的状态为:区间[l,r][l,r]已经安排好了,00:父亲节点是l1l-1,11:父亲节点是r+1r+1.

如何将这两个区间合并呢,显然只有当[l,k][l,k]的父亲节点是k+1k+1,而[k+1,r][k+1,r]的父亲节点是r+1r+1的时候可行,以及[l,k][l,k]的父亲节点是l1l-1,[k+1,r][k+1,r]的父亲节点是kk的时候可行.还有一种是左边和右边的匹配和右边与左边的匹配的情况~

code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int mod=998244353;
const int N=705;
const int M=2;
 
bool f[N][N][M],cnm[N][N];
int a[N];

void run()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)	scanf("%d",&a[i]);
	for(int i=0;i<=n+1;i++)
		for(int j=0;j<=n+1;j++)
			if(__gcd(a[i],a[j])!=1)	cnm[i][j]=true;
	for(int i=1;i<=n;i++)
	{
		if(cnm[i][i-1])	f[i][i][0]=true;
		if(cnm[i][i+1])	f[i][i][1]=true;
	}
	for(int len=2;len<=n;len++)
	{
		for(int l=1;l+len-1<=n;l++)
		{
			int r=l+len-1;
			for(int k=l;k<r;k++)
			{
				f[l][r][0]|=(f[l][k][0]&f[k+1][r][0])|(f[l][r-1][1]&cnm[l-1][r]);
				f[l][r][1]|=(f[l][k][1]&f[k+1][r][1])|(f[l+1][r][0]&cnm[l][r+1]);
			}
		}
	}

	if(f[1][n][0]|f[1][n][1])	puts("Yes");
	else						puts("No");
}
 
int main()
{
	int T=1;
//	scanf("%d",&T);
	while(T--)	run(); 
	return 0;
}
/*

*/