codevs 2241 排序二叉树
★ 输入文件：bstree.in 输出文件：bstree.out 简单对比
时间限制：1 s 内存限制：128 MB
【问题描述】
一个边长为n的正三角形可以被划分成若干个小的边长为1的正三角形，称为单位三角形。
如右图，边长为3的正三角形被分成三层共9个小的正三角形，我们把它们从顶到底，从左到右以1～9编号，见右图。同理，边长为n的正三角形可以划分成n2个单位三角形。
四个这样的边长为n的正三角形可以组成一个三棱锥。我们将正三棱锥的三个侧面依顺时针次序（从顶向底视角）编号为A, B, C，底面编号为D。侧面的A, B, C号三角形以三棱锥的顶点为顶，底面的D号三角形以它与A，B三角形的交点为顶。左图为三棱锥展开后的平面图，每个面上标有圆点的是该面的顶，该图中侧面A, B, C分别向纸内方向折叠即可还原成三棱锥。我们把这A，B、C、D四个面各自划分成n2个单位三角形。
对于任意两个单位三角形，如有一条边相邻，则称它们为相邻的单位三角形。显然，每个单位三角形有三个相邻的单位三角形。现在，把1—4n2分别随机填入四个面总共4n2个单位三角形中。
现在要求你编程求由单位三角形组成的最大排序二叉树。所谓最大排序二叉树，是指在所有由单位三角形组成的排序二叉树中节点最多的一棵树．对于任一单位三角形，可选它三个相邻的单位三角形中任意一个作为父节点，其余两个分别作为左孩子和右孩子。当然，做根节点的单位三角形不需要父节点，而左孩子和右孩于对于二叉树中的任意节点来说并不是都必须的。
【输入】
输入文件为bstree.in。其中第一行是一个整数n(1<=n<=18)，随后的4n2个数，依次为三棱锥四个面上所填的数字。
【输出】
输出文件为bstree.out。其中仅包含一个整数，表示最大的排序二又树所含的节点数目。
【样例输入】
3
19 33 32 31 29 3 5 4 30
22 24 20 21 12 24 23 34 35
14 13 15 26 18 17 8 16 27
11 10 9 1 28 7 2 6 36
【样例】
输入文件对应下图：
【样例输出】
17
【提示】
输出样例文件对应的最大排序二叉树如下图所示：
/*正解代码：我给加了注解，建立排序二叉树的左右子树的时候，一定要注意建立的上下界，否则就不是排序二叉树*/
/*
【算法分析】
在讨论问题的解法之前，我们先来看看二叉排序树的性质。
二叉排序树是一棵满足下列性质的二又树：
性质1 它或是一棵空树，或是一棵二叉树，满足左子树的所有结点的值都小于根结点的值，右子树的所有结点的值都大于根结点的值；
性质2 它若有子树，则它的子树也是二叉排序树。
根据性质1，我们可以知道，二叉排序树的左右子树是互不交叉的。也就是说，如果确定了根结点，那么我们就可以将余下的结点分成两个集合，其中一个集合的元素可能在左子树上，另一集合的元素可能在右子树上，而没有一个结点同时可以属于两个集合。这一条性质，满足了无后效性的要求，正因为二叉排序树的左右子树是互不交叉的，所以如果确定根结点后，求得的左子树，对求右子树是毫无影响的。因此，如果要使排序树尽可能大，就必须满足左右子树各自都是最大的，即局部最优满足全局最优。
根据性质2，二叉排序树的左右子树也是二叉排序树。而前面已经分析得到，左右子树也必须是极大的。所以，求子树的过程也是一个求极大二叉排序树的过程，是原问题的一个子问题。那么，求二叉排序树的过程就可以分成若干个阶段来执行，每个阶段就是求一棵极大的二叉排序子树。
由此，我们看到，本题中，二叉排序树满足阶段性（性质2）和无后效性（性质1），可以用动态规划解决。
下面来看具体解决问题的方法。
不用说，首先必须对给出的正三棱锥建图，建成一张普通的无向图。
根据正三棱锥中结点的性质，每个结点均与三个结点相连。而根据二叉排序树的性质，当一个结点成为另一个结点的子结点后，它属于左子树还是右子树也就确定下来了。所以，可以对每个结点进行状态分离，分离出三种状态——该结点作为与它相连的三个结点的子结点时，所得的子树的状态。但是，一个子结点可以根据它的父结点知道的仅仅是该子树的一个界（左子树为上界，右子树为下界），还有一个界不确定，所以还需对分离出来的状态再进行状态分离，每个状态代表以一个值为界（上界或下界）时的子树状态。
确定了状态后，我们要做的事就是推出状态转移方程。
前面已经提到，一个极大的二叉排序树，它的左右子树也必须是极大的。因此，如果我们确定以结点n为根结点，设所有可以作为它左子结点的集合为N1，所有可以作为它右子结点的集合为N2，则以n为根结点、结点大小在区间[l, r]上的最大二叉排序树的结点个数为：
【动态规划】排序二叉树
我们所要求的最大的二叉排序树的结点个数为：【动态规划】排序二叉树
从转移方程来看，我们定义的状态是三维的。那么，时间复杂度理应为O(n3)。其实并非如此。每个结点的状态虽然包含下界和上界，但是不论是左子结点还是右子结点，它的一个界取决于它的父结点，也就是一个界可用它所属的父结点来表示，真正需要分离的只有一维状态，要计算的也只有一维。因此，本题时间复杂度是O(n2)（更准确的说应该是O(3n2)）。
此外，由于本题呈现一个无向图结构，如果用递推形式来实现动态规划，不免带来很大的麻烦。因为无向图的阶段性是很不明显的，尽管我们从树结构中分出了阶段。不过，实现动态规划的方式不仅仅是递推，还可以使用搜索形式——记忆化搜索。用记忆化搜索来实现本题的动态规划可以大大降低编程复杂度。
*/
/*----------------代码----------------*/
#include<iostream>
#include<cstdio>
using namespace std;
const int Limitn=+;
const int Limitpoint=+;
int n;
int s[][][];
int c[Limitpoint][];
bool vis[Limitpoint][Limitpoint];
int f[Limitpoint][][Limitpoint];
int best;
void init()
{
scanf("%d",&n);/*s[k][i][j]，第k个三角形的第i行的第j个*/
for (int k=;k<=;k++)
for (int i=;i<=n;i++)
for (int j=;j<=i*-;j++)
scanf("%d",&s[k][i][j]);
}
void link(int a,int b)
{
if (!vis[a][b])
{
vis[a][b]=;
c[a][++c[a][]]=b;/*邻接表建边，a不是节点的编号，而是一个数*/
}
if (!vis[b][a])
{
vis[b][a]=;
c[b][++c[b][]]=a;
}
}
void make_graph()
{
for (int k=;k<=;k++)
for (int i=;i<n;i++)
for (int j=;j<i*-;j++)
{/*三角形内部建边*/
link(s[k][i][j],s[k][i][j-]);
link(s[k][i][j],s[k][i][j+]);
if (j%)
link(s[k][i][j],s[k][i+][j+]);
else
link(s[k][i][j],s[k][i-][j-]);
}
for (int k=;k<=;k++)
for (int j=;j<=n*-;j+=)
{/*三角形最后一层建边*/
link(s[k][n][j],s[k][n][j-]);
link(s[k][n][j],s[k][n][j+]);
link(s[k][n][j],s[k][n-][j-]);
}
for (int k=,i=;k<=n;k++,i++)
{/*相邻的棱三角形建边*/
link(s[][i][],s[][i][i*-]);
link(s[][i][i*-],s[][i][]);
link(s[][i][i*-],s[][i][]);
}
for (int j=;j<=n*-;j+=)
{/*其他三角形与第四个三角形建边*/
link(s[][n][j],s[][n-(j/)][]);
link(s[][n][j],s[][j/+][((j/)+)*-]);
link(s[][n][j],s[][n][n*-j]);
}
}
int tree_max(int i,int limit1,int limit2)
{
int from=;/*找出i的父亲。防止又走回去*/
while (c[i][from]!=limit2) from++;
if (f[i][from][limit1]>) return f[i][from][limit1];/*记忆化搜索*/
int l,r;
if (limit1>limit2)/*建立右子树的边界*/
{
l=limit2+;
r=limit1;
}
else/*建立左子树的边界*/
{
l=limit1;
r=limit2-;
}
int lmax=,rmax=;
for (int j=;j<=;j++)/*枚举当前点的所有邻接点，不找到父亲，而且符合上下边界*/
if (j!=from && (l<=c[i][j] && c[i][j]<=r))
if (c[i][j]<i)/*建立左子树*/
lmax=max(lmax,tree_max(c[i][j],l,i));
else/*建立右子树*/
rmax=max(rmax,tree_max(c[i][j],r,i));
f[i][from][limit1]=lmax+rmax+;
return f[i][from][limit1];
}
void dfs()
{
best=;
for (int i=;i<=n*n*;i++)/*枚举所有点*/
{
int lmax=,rmax=;
for (int j=;j<=;j++)
if (c[i][j]<i)/*c[i][j]比i小，就建立左子树*/
lmax=max(lmax,tree_max(c[i][j],,i));
else
rmax=max(rmax,tree_max(c[i][j],n*n*,i));
best=max(best,lmax+rmax+);/*别忘了加上它本身的根节点*/
}
}
int main()
{ init();
make_graph();
dfs();
printf("%d\n",best);
return ;
}
我的代码：
#include<iostream>
using namespace std;
#include<cstdio>
#include<cstdlib>
#define Njd 2000
#include<cstring>
#define K 5
#define L 20
int gra[K][L][L<<];
int edge[Njd][];
int f[Njd][K][Njd]={};
int n,ans=;
bool vis[Njd][Njd]={};
void add_edge(int a,int b)
{
if(!vis[a][b])
{
vis[a][b]=true;
edge[a][++edge[a][]]=b;
}
if(!vis[b][a])
{
vis[b][a]=true;
edge[b][++edge[b][]]=a;
}
}
void input()
{
scanf("%d",&n);
for(int i=;i<=;++i)
for(int j=;j<=n;++j)
for(int k=;k<=(*j-);++k)
scanf("%d",&gra[i][j][k]);
}
void build_graph()
{
for(int i=;i<=;++i)
for(int j=;j<n;++j)
for(int k=;k<=(*j-);++k)
{
add_edge(gra[i][j][k],gra[i][j][k-]);
add_edge(gra[i][j][k],gra[i][j][k+]);
if(k%==)
{
add_edge(gra[i][j][k],gra[i][j-][k-]);
}
else add_edge(gra[i][j][k],gra[i][j+][k+]); }
for(int k=;k<=;++k)
for(int j=;j<=(*n-);j+=)
{
add_edge(gra[k][n][j],gra[k][n][j-]);
add_edge(gra[k][n][j],gra[k][n][j+]);
add_edge(gra[k][n][j],gra[k][n-][j-]);
}
for(int i=;i<=n;++i)
{
add_edge(gra[][i][*i-],gra[][i][]);
add_edge(gra[][i][],gra[][i][*i-]);
add_edge(gra[][i][*i-],gra[][i][]);
}
for(int i=;i<=n;++i)
{
add_edge(gra[][i][*i-],gra[][n][*i-]);
add_edge(gra[][i][],gra[][n][*n-(*i-)]);
add_edge(gra[][n][*i-],gra[][n][*n-(*i-)]);
}
}
int memory_dfs(int k,int limit1,int limit2)
{
int from=;
while(edge[k][from]!=limit2)
{
from++;
}
if(f[k][from][limit1]>)
return f[k][from][limit1];
int l,r;
if(limit1>limit2)
{
r=limit1;l=limit2+;
}
else {
l=limit1;r=limit2-;
}
int lmax=,rmax=;
for(int j=;j<=;++j)
{
if(j!=from&&edge[k][j]>=l&&edge[k][j]<=r)
{
if(edge[k][j]<k)
lmax=max(lmax,memory_dfs(edge[k][j],l,k));
else rmax=max(rmax,memory_dfs(edge[k][j],r,k)); } }
f[k][from][limit1]=lmax+rmax+;
return f[k][from][limit1];
}
int main()
{
input();
build_graph();
ans=;
int lmax=,rmax=;
for(int i=;i<=n*n*;++i)
{
lmax=;rmax=;
for(int j=;j<=;++j)
{
if(edge[i][j]>&&edge[i][j]<i)
lmax=max(lmax,memory_dfs(edge[i][j],,i));
else rmax=max(rmax,memory_dfs(edge[i][j],n*n*,i));
}
ans=max(ans,lmax+rmax+);
}
printf("%d\n",ans);
return ;
}