9-02 901 views
题意:给定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)
- Ceph客户端缓存一致性分析 - 2019年6月21日
- CephFS:什么是CAPS? - 2019年6月21日
- Ceph集群快速搭建教程 - 2019年6月20日