传送门

题意:给定n个整数,问是否能生成一棵BST(二分查找树,左子树都比它小,右子树都比它大),并且有边相连的点权的gcd>1。

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

关键:若[l,r]是左子树,它的父节点必定是r+1,若是右子树,父节点必定是l-1。
#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;
}
Latest posts by 青鸟千秋 (see all)

牛客网暑期多校第五场E room(费用流)

传送门 题意:有n个宿舍,每个宿舍住4个人,给定去年n个宿舍的人员构成,今年n个4人组合的情况,求最少几个人需要搬寝室。 思路:转化为最小费用最大流解...

阅读全文

HDU-4091 Zombie’s Treasure Chest(暴力)

传送门 题意:有一个容量为n的箱子,和无限多的两种珠宝,体积和价值分别是s1,v1,s2,v2,求能装下的最大价值。 思路:直接暴力枚举会TLE,先计算s1 s2的LC...

阅读全文

HDU-6299 Balanced Sequence(贪心)

传送门 题意:有n个字符串,每个字符串仅包含'(‘和’)’,可以按某种方法将这n个字符串连接起来,求最后字符串能完全匹配的子串的长度。 ...

阅读全文

欢迎留言