[CF1025D]Recovering BST

DP 二叉搜索树

题面

给出一些数，若要求两数$gcd>1$才能连边，询问他们是否能构成一棵二叉搜索树。

• $n\leq700$

解析

如果没注意到二叉搜索树这一条件，这题绝对做不出来。。。

二叉搜索树的定义是，对同一节点，左儿子权值比它小，右儿子权值比它大。
于是有一个很重要的性质，中序遍历上点权从小到大。

可以得出推论：

• 一棵子树（在中序遍历上可视为一段区间$[l,r]$），把它作为左儿子，根结点的父亲一定为$r+1$；把它作为右儿子，根节点父亲一定为$l-1$。

然而注意到，如果暴力设$f[i][j][k][0/1]$表示以$k$为根，$[i,j]$作为其左/右儿子是否合法是会$MLE$，而且有许多无效状态。

于是需应用上面推论，设两个判合法性的数组：

• $L[i][j]$表示区间$[i,j-1]$作为$j$的左儿子是否合法
• $R[i][j]$表示区间$[i+1,j]$作为$j$的右儿子是否合法

转移：
设$k$为区间$[i,j]$的根，
如果$L[i][k]=1$且$r[k][j]=1$，则该状态合法，可以转移；
没地方转移了就$puts("Yes")$。
如果$k$可以与$l-1$相连，说明以$l-1$为根，$[l,r]$为右儿子的状态合法。
如果$k$可以与$r+1$相连，说明以$r+1$为根，$[l,r]$为左儿子的状态合法。

Ps:联想到了另一道题

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
il ll gi()
{
  re ll x=0,p=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') p=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return p*x;
}
const int N=710;
int n,a[N],f[N][N],L[N][N],R[N][N];
int main()
{
  ios::sync_with_stdio(false);
  cin>>n;
  for(int i=1;i<=n;i++) cin>>a[i],L[i][i]=R[i][i]=1;
  fp(i,1,n) fp(j,i,n) if(__gcd(a[i],a[j])>1) f[i][j]=f[j][i]=1;
  fq(l,n,1)
    fp(r,l,n)
    fp(k,l,r)
    if(L[l][k]&&R[k][r])
      {
    if(l==1&&r==n) {puts("Yes");return 0;}
    if(f[l-1][k]) R[l-1][r]=1;
    if(f[k][r+1]) L[l][r+1]=1;
      }
  puts("No");
  return 0;
}