Recovering BST

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

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

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

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

不妨令$dpdp$的状态为:区间$[l,r][l,r]$已经安排好了,$00$:父亲节点是$l-1l-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]$的父亲节点是$l-1l-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;
}
/*

*/