CF1025D Recovering BST 题解

题意

$ $ 给定一个长度为 (n) （ (2le nle 700) ）的升序排列。问是否有办法用这几个数作为点权构成一棵 BST 使得这棵 BST 所有边连接的两点的点权互质。

题解

(~~~~) 我们知道 BST 的中序遍历一定是升序排列的，因此这个序列就是一棵二叉树的中序遍历。而当我们钦定一个升序区间中某一个节点为该区间子树的根节点时，这个子树根节点的左右子树就确定了。而把这个操作逆向过来，就是一个区间 DP 的过程。

(~~~~) 本题有一些不一样，看到 (n) 很小，可以往 (mathcal{O(n^3)}) 的算法去想。

(~~~~) 如果一开始没有想到，可以考虑用暴力一点的算法优化上来。不难想到一个 (n^4) 的 DP ，设： (dp_{i,j,k}) 表示区间 ([l,r]) 以整个序列的第 (k) 个元素为根时该区间的合法性。

(~~~~) 很容易想到如何转移，用 (n^2) 枚举区间，(n) 枚举当前区间子树的根节点，(n) 枚举左右区间是否有满足条件的根节点即可。

(~~~~) 那我们怎么优化这个过程呢？发现 (n^2) 的枚举区间肯定优化不动，那就往另外的两个过程想。

(~~~~) 发现一个区间 ([l,r]) 其父节点只可能是 (l-1) 或 (r+1) 。可以利用这个性质进行 DP

(~~~~) 正解部分： 定义： (dp_{i,j,k}) ，当 (k=0) 时表示 ([l,r-1]) 的父节点是 (r) 的合法性，当 (k=1) 时表示 ([l+1,r]) 的父节点是 (l)。考虑一个已知的状态 (dp_{l,r,k}) 能扩展出的状态，可以得到转移方程。

[Large dp_{l-1,r,1}=dp_{l,k,0} ~ & ~ dp_{k,r,1} ~ & ~ (a_{l-1},a_{k}) ot= 1 ]

[Large dp_{l,r+1,0}=dp_{l,k,0} ~ & ~ dp_{k,r,1} ~ & ~ (a_{r+1},a_{k}) ot =1 ]

(~~~~) 初值：(dp_{i,i,0},dp_{i,i,1} (1 le i le n)) 均为 (1)。答案：当某次转移到区间 ([1,n]) 时满足上面两个转移方程的前两个条件即可。

(~~~~) 然后大力转移就可以了，另外还要注意一些细节，具体见代码。

代码

#include <cstdio>
#include <algorithm>
using namespace std;
int gcd(int a,int b)
{
	if(b==0) return a;
	else return gcd(b,a%b);
}
int arr[705];
bool f[705][705],dp[705][705][2];//dp[l][r][k]:区间 [l,r] 在父节点为 r(k=0)时的合法性与在父节点为 l(k=1)时的合法性 
int main() {
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&arr[i]),dp[i][i][0]=dp[i][i][1]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			if(gcd(arr[i],arr[j])!=1) f[i][j]=f[j][i]=true;// n^2预处理一下，不然每次都有 log 也受不起。 
		}
	}
	for(int l=n;l>=1;l--)
	for(int r=l;r<=n;r++)
	for(int k=l;k<=r;k++)
	{
		if(dp[l][k][0]&&dp[k][r][1])
		{
			if(l==1&&r==n)
			{
				puts("Yes");
				return 0;	
			}
			if(f[l-1][k]) dp[l-1][r][1]=true;
			if(f[r+1][k]) dp[l][r+1][0]=true;
		}
	}
	puts("No");
	return 0;
}