【非原创】codeforces 1025D - Recovering BST【区间dp+二叉搜索树】

题目：戳这里

题意：给一个不下降序列，有n个数。问能否构造一个二叉搜索树，满足父亲和儿子之间的gcd>1.

解题思路：其实这题就是构造个二叉搜索树，只不过多了个条件。主要得了解二叉搜索树的性质，比如一段区间[l,r]，这段区间要么是[l-1]的右子树，要么是[r+1]的左子树。（二叉树中左子树都比根小，右子树都比根大

根据这个性质，用dfs构造二叉搜索树，构造的时候判断儿子和父亲的gcd是否大于1即可。

 

看到一个博客代码写的很漂亮，学习一下。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 700 + 10;
#define lowbit(x) x&-x
int gcd(int a, int b) {
    return b?gcd(b,a%b):a;
}
int dp[maxn][maxn][2];
int a[maxn];
bool dfs(int l, int r, int x) {
    if(l > r) return 1;
    if(dp[l][r][x] != -1) return dp[l][r][x];
    int y=(x?a[r+1]:a[l-1]);
    for(int i = l; i <= r; ++i) {
        if(gcd(y, a[i]) == 1) continue;
        if(dfs(l, i-1, 1) && dfs(i+1,r,0)) {
            return dp[l][r][x] = 1;

        }
    }
    return dp[l][r][x] = 0;

}
int main() {
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    memset(dp, -1, sizeof(dp));
    for(int i = 1; i <= n; ++i) {
        if(dfs(1, i - 1, 1) && dfs(i + 1, n, 0)) {
            puts("Yes");
            return 0;
        }
    }
    puts("No");
    return 0;
}