算法

區(qū)間動(dòng)態(tài)規(guī)劃

題目描述

給出一串?dāng)?shù)字，詢問是否可以構(gòu)造為符合條件的二叉搜索樹。

解題思路

使用區(qū)間動(dòng)態(tài)規(guī)劃，f[i][j]表示從i到j(luò)可構(gòu)造為二叉搜索樹，而l[i][j]、r[i][j]分別表示可構(gòu)造二叉搜索樹并且分別以最左端、最右端為根節(jié)點(diǎn)，因此有轉(zhuǎn)移方程如下：
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
*/

題目總結(jié)

區(qū)間DP的題目首先在于，要看出來這是一道區(qū)間DP，其次注意定義每個(gè)區(qū)間的含義，以及轉(zhuǎn)移方程；
最后不要寫錯(cuò)枚舉區(qū)間的補(bǔ)步驟。

題目原文

題目描述

題目描述在瑞神大戰(zhàn)宇宙射線中我們了解到了宇宙狗的厲害之處，雖然宇宙狗兇神惡煞，但是宇宙狗有一個(gè)很可愛的女朋友。

最近，他的女朋友得到了一些數(shù)，同時(shí)，她還很喜歡樹，所以她打算把得到的數(shù)拼成一顆樹。

這一天，她快拼完了，同時(shí)她和好友相約假期出去玩。貪吃的宇宙狗不小心把樹的樹枝都吃掉了。所以恐懼包圍了宇宙狗，他現(xiàn)在要恢復(fù)整棵樹，但是它只知道這棵樹是一顆二叉搜索樹，同時(shí)任意樹邊相連的兩個(gè)節(jié)點(diǎn)的gcd(greatest common divisor)都超過1。

但是宇宙狗只會(huì)發(fā)射宇宙射線，他來請求你的幫助，問你能否幫他解決這個(gè)問題。

補(bǔ)充知識(shí)：
GCD：最大公約數(shù)，兩個(gè)或多個(gè)整數(shù)共有約數(shù)中最大的一個(gè)，例如8和6的最大公約數(shù)是2。
一個(gè)簡短的用輾轉(zhuǎn)相除法求gcd的例子：

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

輸入描述

輸入第一行一個(gè)t，表示數(shù)據(jù)組數(shù)。
對于每組數(shù)據(jù)，第一行輸入一個(gè)n，表示數(shù)。
的個(gè)數(shù)接下來一行有n個(gè)數(shù)，輸入保證是升序的。

輸出描述

每組數(shù)據(jù)輸出一行，如果能夠造出來滿足題目描述的樹，輸出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可構(gòu)造如下圖

樣例1

數(shù)據(jù)組成

數(shù)據(jù)點(diǎn)	t	n
1，2，3	5	15	109
4，5，6	5	35	109
7，8，9，10	5	700	109