【CF1025D】Recovering BST

题面

https://www.luogu.org/problem/CF1025D

题解

容易想到$f[l][r][x]$为区间$[l..r]$是否可以建成一颗根为$x$的$BST$，枚举$x$后，把区间剖成独立的两半，然后逐个检查可以做左右子树的根。时间复杂度$O(n^4)$。

考虑$mbox{Gloid}$爷的神奇优化（我一开始以为是从$gcd$的性质上考虑的），设$f[l][r][0/1]$表示区间$[l..r]$是否可以以$l-1/r+1$为根，然后枚举根节点，随便转移一下就可以辣！

#include<cstdio>
#include<cstring>
#include<iostream>
#define ri register int
#define N 705
#define LL long long
using namespace std;

bool f[N][N][2],g[N][N];
int a[N];
int n,k;

int gcd(int a,int b) {
  if (!b) return a;
  return gcd(b,a%b);
}

int check() {
  for (ri i=1;i<=n;i++) if (f[1][i-1][1] && f[i+1][n][0]) return 1;
  return 0;
}

int main() {
  cin>>n;
  for (ri i=1;i<=n;i++) cin>>a[i];
  for (ri i=1;i<=n;i++)
    for (ri j=1;j<=n;j++) if (gcd(a[i],a[j])!=1) g[i][j]=1;
  for (ri i=0;i<=n;i++) f[i+1][i][0]=1,f[i+1][i][1]=1;
  for (ri len=0;len<n;len++) 
    for (ri l=1;l+len<=n;l++) {
      int r=l+len;
      for (ri i=l;i<=r;i++) f[l][r][0]|=(g[l-1][i])&&(f[l][i-1][1])&&(f[i+1][r][0]);
      for (ri i=l;i<=r;i++) f[l][r][1]|=(g[r+1][i])&&(f[l][i-1][1])&&(f[i+1][r][0]);
    }
  if (check()) printf("Yes"); else printf("No");
  return 0;
}