【Week16CSP模拟IV-C】宇宙狗的危机

算法

区间动态规划

题目描述

给出一串数字，询问是否可以构造为符合条件的二叉搜索树。

解题思路

使用区间动态规划，f[i][j]表示从i到j可构造为二叉搜索树，而l[i][j]、r[i][j]分别表示可构造二叉搜索树并且分别以最左端、最右端为根节点，因此有转移方程如下：
if(l[st][k]&&r[k][nd]){
f[st][nd]=1;
if(vis[st-1][k]) r[st-1][nd]=1;//如果能以st-1为根
if(vis[k][nd+1]) l[st][nd+1]=1;//如果能以nd+1为根
}

代码

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1010;
int a[maxn];
bool vis[maxn][maxn];
bool l[maxn][maxn],r[maxn][maxn],f[maxn][maxn];
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); }

bool maketree(int n) {
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(gcd(a[i],a[j])>1){
                vis[i][j]=1;
            }
        }
    }
    for(int i=1;i<=n;i++){
        f[i][i]=l[i][i]=r[i][i]=1;
    }
    for(int i=1;i<=n;i++){
        for(int st=1;st+i-1<=n;st++){
            int nd=st+i-1;
            for(int k=st;k<=nd;k++){
                if(l[st][k]&&r[k][nd]){
                    f[st][nd]=1;
                    if(vis[st-1][k]) r[st-1][nd]=1;//如果能以st-1为根
                    if(vis[k][nd+1]) l[st][nd+1]=1;//如果能以nd+1为根
                }
            }
        }
    }
    return f[1][n];
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        memset(vis, 0, sizeof vis);
        memset(r, 0, sizeof r);
        memset(l, 0, sizeof l);
        memset(f, 0, sizeof f);
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        if (maketree(n)) {
            cout << "Yes" << endl;
        }
        else {
            cout << "No" << endl;
        }
    }
    return 0;
}
/*
1
6
3 6 9 18 36 108
*/

题目总结

区间DP的题目首先在于，要看出来这是一道区间DP，其次注意定义每个区间的含义，以及转移方程；
最后不要写错枚举区间的补步骤。

题目原文

题目描述

题目描述在瑞神大战宇宙射线中我们了解到了宇宙狗的厉害之处，虽然宇宙狗凶神恶煞，但是宇宙狗有一个很可爱的女朋友。

最近，他的女朋友得到了一些数，同时，她还很喜欢树，所以她打算把得到的数拼成一颗树。

这一天，她快拼完了，同时她和好友相约假期出去玩。贪吃的宇宙狗不小心把树的树枝都吃掉了。所以恐惧包围了宇宙狗，他现在要恢复整棵树，但是它只知道这棵树是一颗二叉搜索树，同时任意树边相连的两个节点的gcd(greatest common divisor)都超过1。

但是宇宙狗只会发射宇宙射线，他来请求你的帮助，问你能否帮他解决这个问题。

补充知识：
GCD：最大公约数，两个或多个整数共有约数中最大的一个，例如8和6的最大公约数是2。
一个简短的用辗转相除法求gcd的例子：

intgcd(int a,int b){return b ==0? a :gcd(b,a%b);}

输入描述

输入第一行一个t，表示数据组数。
对于每组数据，第一行输入一个n，表示数。
的个数接下来一行有n个数 $a_i$ ，输入保证是升序的。

输出描述

每组数据输出一行，如果能够造出来满足题目描述的树，输出Yes，否则输出No。
无行末空格。

样例输入1

1
6
3 6 9 18 36 108

样例输出1

Yes

样例输入2

2
2
7 17
9
4 8 10 12 15 18 33 44 8

样例输出2

No
Yes

样例解释

样例1可构造如下图

样例1

数据组成

数据点	t	n	$a_i$
1，2，3	5	15	10⁹
4，5，6	5	35	10⁹
7，8，9，10	5	700	10⁹