CF-1025D Recovering BST(区间dp)

传送门

思路：区间dp，dp[l][r][1/0]表示区间[l,r]是否可以是一棵合法的左/右子树。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

typedef long long ll;
const int INF=0x3f3f3f3f;
const ll mod=1e9+7;

int a[705];
bool d[705][705];
int dp[705][705][2];
int n;
bool flag;
int dfs(int l,int r,int e)
{
    if (l>r)
        return 1;
    if (dp[l][r][e]!=-1)
        return dp[l][r][e];
    int fa;
    if (e)///当前区间是左子树
        fa=r+1;
    else///当前区间是右子树
        fa=l-1;
    for (int i=l;i<=r;i++)
    {
        if (d[fa][i]&&dfs(l,i-1,1)&&dfs(i+1,r,0))
            return dp[l][r][e]=1;
    }
    return dp[l][r][e]=0;
}
int main()
{
    scanf("%d",&n);
    for (int i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
        d[i][0]=d[0][i]=true;///可以作为树根
    }
    for (int i=1; i<=n; i++)
    {
        for (int j=i+1;j<=n;j++)
        {
            if (__gcd(a[i],a[j])>1)
                d[i][j]=d[j][i]=true;
            else
                d[i][j]=d[j][i]=false;
        }
    }
    memset(dp,-1,sizeof dp);
    if (dfs(1,n,0))///假设整棵树为右子树，使树根的父节点为0
        printf("Yes\n");
    else
        printf("No\n");
    return 0;
}