记录编号	175093	评测结果	WWWWWWWWWW
题目名称	排序二叉树	最终得分	0
用户昵称	NVIDIA	是否通过	未通过
代码语言	C++	运行时间	0.245 s
提交时间	2015-08-04 16:08:59	内存使用	22.20 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<fstream>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<queue>
#include<iomanip>
using namespace std;
const int Limitn=18+2;
const int Limitpoint=1296+4;
int n;
int s[5][20][40];
int c[Limitpoint][4];
bool vis[Limitpoint][Limitpoint];
int f[Limitpoint][4][Limitpoint];
int best;
int tree_max(int i,int limit1,int limit2)
{
    int from=1;
    while (c[i][from]!=limit2) 
		from++;
    if (f[i][from][limit1]>0) 
		return f[i][from][limit1];
    int l,r;
    if (limit1>limit2)
    {
        l=limit2+1;
        r=limit1;
    }
    else
    {
        l=limit1;
        r=limit2-1;
    }
    int lmax=0,rmax=0;
    for (int j=1;j<=3;j++)
        if (j!=from&&(l<=c[i][j]&&c[i][j]<=r))
            if (c[i][j]<i)
                lmax=lmax>tree_max(c[i][j],l,i)?tree_max(c[i][j],l,i):lmax;
            else
                rmax=rmax>tree_max(c[i][j],r,i)?tree_max(c[i][j],r,i):lmax;
    f[i][from][limit1]=lmax+rmax+1;
    return f[i][from][limit1];
}
void init()
{
    scanf("%d",&n);
    for (int k=1;k<=4;k++)
        for (int i=1;i<=n;i++)
            for (int j=1;j<=i*2-1;j++)
                scanf("%d",&s[k][i][j]);
}
void link(int a,int b)
{
    if (!vis[a][b])
    {
        vis[a][b]=1;
        c[a][++c[a][0]]=b;
    }
    if (!vis[b][a])
    {
        vis[b][a]=1;
        c[b][++c[b][0]]=a;
    }
}
void make_graph()
{
    for (int k=1;k<=4;k++)
        for (int i=2;i<n;i++)
            for (int j=2;j<i*2-1;j++)
            {
                link(s[k][i][j],s[k][i][j-1]);
                link(s[k][i][j],s[k][i][j+1]);
                if (j%2)
                    link(s[k][i][j],s[k][i+1][j+1]);
                else
                    link(s[k][i][j],s[k][i-1][j-1]);
            }
    for (int k=1;k<=4;k++)
        for (int j=2;j<=n*2-1;j+=2)
        {
            link(s[k][n][j],s[k][n][j-1]);
            link(s[k][n][j],s[k][n][j+1]);
            link(s[k][n][j],s[k][n-1][j-1]);
        }
    for (int k=1,i=1;k<=n;k++,i++)
    {
        link(s[1][i][1],s[3][i][i*2-1]);
        link(s[1][i][i*2-1],s[2][i][1]);
        link(s[2][i][i*2-1],s[3][i][1]);
    }
    for (int j=1;j<=n*2-1;j+=2)
    {
        link(s[1][n][j],s[4][n-(j/2)][1]);
        link(s[2][n][j],s[4][j/2+1][((j/2)+1)*2-1]);
        link(s[3][n][j],s[4][n][n*2-j]);
    }
}

void dfs()
{
    best=0;
    for(int i=1;i<=n*n*4;i++)
    {
        int lmax=0,rmax=0;
        for (int j=1;j<=3;j++)
            if (c[i][j]<i)
               lmax=lmax>tree_max(c[i][j],1,i)?tree_max(c[i][j],1,i):lmax;
            else
                rmax=rmax>tree_max(c[i][j],n*n*4,i)?tree_max(c[i][j],n*n*4,i):lmax;
        best=best>lmax+rmax+1?lmax+rmax+1:best;
    }
}
int main()
{
    freopen("bstree.in","r",stdin);
    freopen("bstree.out","w",stdout);
    init();
    make_graph();
    dfs();
    printf("%d\n",best);
   return 0;
}