题解 P1267 【排序二叉树】

· · 题解

首先，我们在相邻的小三角形之间建边，这样问题就转化成了在图内选点，使其为一颗排序二叉树。

对于一个根节点，它的取值范围毫无疑问是[1,4n^2];设它的值为x，那么它的左儿子的取值范围就是[1,x-1],右儿子的取值范围则是[x+1,4n^2]。由此我们可以推知对于任意一个点，若它的取值范围为[a,b]，它的值为x，则它的左儿子取值范围为[a,x-1]，右儿子取值范围为[x+1,b]，接下来就只要去枚举与它相邻的点有没有满足条件的就好。

那么f[i][j][k]数组就表示以值为i的节点为根，取值范围为[j,k]时的最大排序二叉树的节点数。然而这空间复杂度为O[(4n^2)^3]，绝对会爆。怎么办呢？

从上一推论我们能看出，节点i（除根之外）的范围边界之一一定与它的父亲有关，因此我们可以将其中一维数组转化为第几个相邻的点，即f[i][j][k]，j表示第几个相邻的点是它的父亲，k则表示它的另一边界。

具体实现详见代码。

#include<bits/stdc++.h>
 using namespace std;
 int n,i,j,k,l,r,ans;
 int ne[1300][3],cnt[1300],f[1300][3][1300],s[5][20][50];
 int read()
{
    int x=0,w=0;char ch=0;
    while (!isdigit(ch)) w|=ch=='-',ch=getchar();
    while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return w?-x:x;
}
 void build(int a,int b){ne[a][cnt[a]++]=b; ne[b][cnt[b]++]=a;}
 int dp(int now,int a,int b)//now为当前节点的值，b为父亲的值，a为另一边界
{
    int fa=0; while(ne[now][fa]!=b)fa++;//寻找父亲是相邻的第几个点
    if(f[now][fa][a])return f[now][fa][a];
    int x,y,l=0,r=0;
    if(a>b)x=b+1,y=a; else x=a,y=b-1;
    for(int i=0;i<3;i++) if(i!=fa&&x<=ne[now][i]&&ne[now][i]<=y)
    {
        if (ne[now][i]<now)l=max(l,dp(ne[now][i],x,now));
        else r=max(r,dp(ne[now][i],y,now));
    }
    f[now][fa][a]=l+r+1;
    return f[now][fa][a];
}//记忆话搜索
 int main()
{
    n=read();
    for(i=1;i<=4;i++)
     for(j=1;j<=n;j++)
      for(k=1;k<j+j;k++) s[i][j][k]=read();
    for(i=1;i<=4;i++)
        for(j=2;j<=n;j++)
        {
            for(k=2;k<j<<1;k+=2)
            {
                build(s[i][j][k],s[i][j-1][k-1]); build(s[i][j][k],s[i][j][k-1]);
                build(s[i][j][k],s[i][j][k+1]);
            }
        }
    for(i=1;i<=n;i++)
    {
        build(s[1][i][1],s[3][i][(i<<1)-1]); 
        build(s[2][i][1],s[1][i][(i<<1)-1]);
        build(s[3][i][1],s[2][i][(i<<1)-1]); 
        build(s[4][i][1],s[1][n][2*n-(i<<1)+1]);
        build(s[4][i][(i<<1)-1],s[2][n][(i<<1)-1]); 
        build(s[4][n][(i<<1)-1],s[3][n][2*n-(i<<1)+1]);
    }//建边
    for(i=1;i<=4*n*n;i++)//枚举根
    {
        l=0; r=0;//记录最大左右子树
        for(j=0;j<3;j++)
         if(ne[i][j]<i)l=max(l,dp(ne[i][j],1,i));
         else r=max(r,dp(ne[i][j],4*n*n,i));
        ans=max(ans,l+r+1);
    }
    printf("%d",ans);
    return 0;
}