【NOIP模拟】遗失的二叉树

题面

小T很喜欢研究树形数据结构，这一天，他的哥哥小Q丢给了小T一个问题：给定一序列，判断其是否为一颗二叉树的中序遍历，对于小T来说，这个问题太简单了，所以哥哥又添加了一个条件：树边连接的两个点的权值不能互质。现在小T对这个问题毫无对策，于是他请你帮他解决这个问题。
每个输入文件包含多组数据。
输入文件仅有一行，第一行一个数字T，表示测试组数
对于每一组测试样例
第一行一个数字n，表示序列长度
第二行有n个数字ai，表示这个序列
输出文件输出T行，如果可以恢复出二叉树，则输出Yes，否则输出No。

分析

这题还是有点遗憾的吧，虽然当时完全没往dp上想，但是我觉得我dfs的暴力的思想是很像dp的思想的。

首先要知道中根序，即左中右。

于是形象来看，感觉是选一些点，把这个序列拉着两头，从选的这个点折一下。

考虑区间dp，L[l][r]表示区间[l,r] 是否可以作为r的左儿子，即L[l][r]表示以r为根 [l,r-1]为左子树是否合法,
R[l][r]表示区间[l,r]是否可以作为l的右儿子，即R[l][r]表示以l为根 [l+1,r]为右子树是否合法,
枚举k与根节点进行转移，那么就可以得到方程:
L[l][r] |= L[l][k]&R[k][r-1]&mp[k][r];
R[l][r] |= L[l+1][k]&R[k][r]&mp[k][l];
最后判断一下存不存在一个i使得(L[1][i]&R[i][n])==1即可

 真正写的时候，我是默认不可行（0），再通过成立的情况染色为可行（1）

代码

#include<bits/stdc++.h>
using namespace std;
#define N 550
int l,r,k,t,n,ok;
int a[N];
int L[N][N],R[N][N],E[N][N];
inline void init()
{
    memset(L,0,sizeof(L));
    memset(R,0,sizeof(R));
    memset(E,0,sizeof(E));
}
inline int gcd(int a,int b)
{return a%b==0?b:gcd(b,a%b);}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        init();ok=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                E[i][j]=(gcd(a[i],a[j])!=1)?1:0;
        for(int i=1;i<=n;i++)L[i][i]=R[i][i]=1;
        for (int x=1;x<n;x++)
         for (int i=1;i<=n;i++)
          {
            int l = i-x, r = i+x;
            if(l >= 1) 
                for(int k=l;k<i;k++) 
                    if(E[i][k] && L[k][l] && R[k][i-1]) L[i][l] = 1;
            if(r <= n) 
                for(int k=i+1;k<=r;k++) 
                    if(E[i][k] && L[k][i+1] && R[k][r]) R[i][r] = 1;
        }            
        for(int i=1;i<=n;i++)
            if((L[1][i]&R[i][n])==1)
                ok=1;
        if(ok)printf("Yes
");
        else   printf("No
");
    }
    
}