CodeForces - 1025D: Recovering BST (区间DP)

Dima the hamster enjoys nibbling different things: cages, sticks, bad problemsetters and even trees!

Recently he found a binary search tree and instinctively nibbled all of its edges, hence messing up the vertices. Dima knows that if Andrew, who has been thoroughly assembling the tree for a long time, comes home and sees his creation demolished, he'll get extremely upset.

To not let that happen, Dima has to recover the binary search tree. Luckily, he noticed that any two vertices connected by a direct edge had their greatest common divisor value exceed 11.

Help Dima construct such a binary search tree or determine that it's impossible. The definition and properties of a binary search tree can be found here.

Input

The first line contains the number of vertices nn (2≤n≤7002≤n≤700).

The second line features nn distinct integers aiai (2≤ai≤1092≤ai≤109) — the values of vertices in ascending order.

Output

If it is possible to reassemble the binary search tree, such that the greatest common divisor of any two vertices connected by the edge is greater than 11, print "Yes" (quotes for clarity).

Otherwise, print "No" (quotes for clarity).

Examples

Input

6
3 6 9 18 36 108

Output

Yes

Input

2
7 17

Output

No

Input

9
4 8 10 12 15 18 33 44 81

Output

Yes

题意：给定一个序列，如果两个数gcd不为1，则可以连边，现在问连边是否可以构造二叉搜索树（左子树的节点值都小于本节点，右子数都大于）。

思路：没想到。看了题解。题解是，区间DP。L[i][j]表示区间(i,j)是否可以作为j+1的左子树，R[i][j]同理。对于L[i][j],我们要找Mid，使得L[i,Mid-1]==true，且R[Mid+1,j]=true，且gcd(a[Mid],a[j+1])>1；此时L[i][j]=1; R数组同理。

（因为大小右分组的关系，那么就用区间来搞。。。好事没毛病。

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

int a[maxn],g[maxn][maxn],l[maxn][maxn],r[maxn][maxn];

int main()

{

    int N,i,j;

    scanf("%d",&N);

    rep(i,,N) scanf("%d",&a[i]);

    rep(i,,N) rep(j,,N) if(i!=j) g[i][j]=(__gcd(a[i],a[j])>);

    rep(i,,N-){

        rep(L,,N-i){

            int R=i+L;

            rep(Mid,L,R){

                if((L<=Mid-?l[L][Mid-]:)&&(R>=Mid+?r[Mid+][R]:)){

                    if(g[L-][Mid]) r[L][R]=;

                    if(g[Mid][R+]) l[L][R]=;

                }

            }

        }

    }

    rep(i,,N){

       if((<=i-?l[][i-]:)&&(N>=i+?r[i+][N]:))

         return puts("Yes"),;

    }

    puts("No");

    return ;

}

巴特西

CodeForces - 1025D: Recovering BST (区间DP)

最新文章

热门文章