bf bf film bf rajwap.biz tamil pussy fingering desi pron video coxhamster.mobi sexy girl video open xvideoimage pornfactory.info bihari sexy video download سكس كلاسيك مترجم pornclassic.info سكس عراقي hindixxvidio porno-zona.com dise murga indian old women nude rajwap.biz srxyvidio www sexy videoes com indiansexmms.me sxsi bf مصريات شراميط pornvuku.net نيك احلي كس malligi hotel donfreeporn.mobi bengalixxxvideo tsmil sex youjizz.sex perfect girl xxx hd any porn porntubemovs.info xxx thumbzilla نيك طيز مترجم 3gpjizz.info سكس فى السجن xossip bengali kamporn.mobi indian sex play forced indian sex video indiansexgate.mobi sleeping girl xnxx classic video com 2beeg.me indiangirlssexvideos

传送门

题意:给定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个字符串连接起来,求最后字符串能完全匹配的子串的长度。 ...

阅读全文

欢迎留言