CF1025D Recovering BST

题目描述

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 (1) .

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.

输入输出格式

输入格式：

The first line contains the number of vertices (n) ( (2 le n le 700) ).

The second line features (n) distinct integers (a_i) ( (2 le a_i le 10^9) ) — the values of vertices in ascending order.

输出格式：

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 (1) , print "Yes" (quotes for clarity).

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

不错的区间DP题。

首先有个简单的区间DP思路

(dp_{i,j,k})表示点(i)根,区间([j,k])的合法性，然后每次枚举两个子区间的根进行转移。

但是我们发现，对于一个区间，它向外转移的时候只判断了根是否和区间左端点的左边一位合法，或者跟右端点的右边一位合法。

这启发我们把这个带入状态。

(L_{i,j})代表区间([i,j])是否有一个跟可以和左端点左边的点连边并且形成合法子树，(R_{i,j})同理

这有点像树形DP中头顶的那条边

转移的时候，枚举子区间是否可以，然后看枚举的根是否可以连出去就可以了

事先预处理连边复杂度就是(O(N^3))

事实上可以记搜+bitset卡过去的，区间DP上界本来就小，记搜再剪剪枝，几乎不可卡。

Code:

#include <cstdio>
#include <algorithm>
const int N=702;
int g[N][N],L[N][N],R[N][N],n,a[N];
int gcd(int x,int y){return y?gcd(y,x%y):x;}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",a+i);
    std::sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
            g[i][j]=g[j][i]=gcd(a[i],a[j])!=1;
        g[i][0]=g[i][n+1]=1;
    }
    for(int i=1;i<=n;i++)
        L[i][i]=g[i][i-1],R[i][i]=g[i][i+1];
    for(int i=n;i;i--)
        for(int j=i+1;j<=n;j++)
            for(int k=i;k<=j;k++)
            {
                if(k==i)
                {
                    L[i][j]|=g[k][i-1]&L[k+1][j];
                    R[i][j]|=g[k][j+1]&L[k+1][j];
                }
                else if(k==j)
                {
                    L[i][j]|=g[k][i-1]&R[i][k-1];
                    R[i][j]|=g[k][j+1]&R[i][k-1];
                }
                else
                {
                    L[i][j]|=R[i][k-1]&L[k+1][j]&g[k][i-1];
                    R[i][j]|=R[i][k-1]&L[k+1][j]&g[k][j+1];
                }
            }
    if(L[1][n]|R[1][n])
        puts("Yes");
    else
        puts("No");
    return 0;
}

2018.10.12