门户网站 流量,特产网站开发的好处,佛山 做网站公司有哪些,电子商务网站设计是什么农民约翰准备购买一群新奶牛。 在这个新的奶牛群中, 每一个母亲奶牛都生两个小奶牛。这些奶牛间的关系可以用二叉树来表示。这些二叉树总共有N个节点(3 N 200)。这些二叉树有如下性质: 描述 每一个节点的度是0或2。度是这个节点的孩子的数目。 树的高度等于K(1 …农民约翰准备购买一群新奶牛。 在这个新的奶牛群中, 每一个母亲奶牛都生两个小奶牛。这些奶牛间的关系可以用二叉树来表示。这些二叉树总共有N个节点(3 N 200)。这些二叉树有如下性质: 描述 每一个节点的度是0或2。度是这个节点的孩子的数目。 树的高度等于K(1 K 100)。高度是从根到最远的那个叶子所需要经过的结点数; 叶子是指没有孩子的节点。 有多少不同的家谱结构? 如果一个家谱的树结构不同于另一个的, 那么这两个家谱就是不同的。输出可能的家谱树的个数除以9901的余数。 格式 PROGRAM NAME: nocows INPUT FORMAT (file nocows.in) 第1行: 两个空格分开的整数, N和K。 OUTPUT FORMAT (file nocows.out) 第 1 行: 一个整数表示可能的家谱树的个数除以9901的余数。 SAMPLE INPUT 5 3SAMPLE OUTPUT 2OUTPUT DETAILS 有5个节点高为3的两个不同的家谱 / \ / \ 和 / \ / \ 分析 这道题因为对树不太熟悉自己没有想出来看的官方的解题报告: 这是一个DP问题。我们所关心的树的性质是深度和节点数所以我们可以做这样一张表table[i][j]表示深度为i、节点数为j的树的个数。根据给定的约束条件j必须为奇数。你如何构造一棵树呢当然是由更小的树来构造了。一棵深度为i、节点数为j的树可以由两个子树以及一个根结点构造而成。当i、j已经选定时我们选择左子树的节点数k。这样我们也就知道了右子树的节点数即j-k-1。至于深度至少要有一棵子树的深度为i-1才能使构造出的新树深度为i。有三种可能的情况左子树深度为i-1 右子树深度小于i-1右子树深度为i-1左子树深度小于i-1左右子树深度都为i-1。事实上当我们在构造一棵深度为i的树时我们只关心使用的子树深度是否为i-1或更小。因此我们使用另一个数组smalltrees[i-2][j]记录所有深度小于i-1的树而不仅仅是深度为i-2的树。知道了上面的这些我们就可以用以下三种可能的方法来建树了 table[i][j] : smalltrees[i-2][k]*table[i-1][j-1-k];// 左子树深度小于i-1右子树深度为i-1
table[i][j] : table[i-1][k]*smalltrees[i-2][j-1-k];// 左子树深度为i-1右子树深度小于i-1
table[i][j] : table[i-1][k]*table[i-1][j-1-k];// 左右子树深度都为i-1 另外如果左子树更小我们可以对它进行两次计数因为可以通过交换左右子树来得到不同的树。总运行时间为O(K*N^2)且有不错的常数因子。 代码 #include cstdio
#include cstdlib
#include cassert
#define MOD 9901
using namespace std;int table[101][202],N,K,c;
int smalltrees[101][202];FILE *finfopen(nocows.in,r);
FILE *foutfopen(nocows.out,w);int main() {fscanf (fin,%d %d,N,K);table[1][1]1;for (int i2;iK;i) {for (int j1;jN;j2)for (int k1;kj-1-k;k2) {if (k!j-1-k) c2; else c1; //判断树的结构是否对称 table[i][j]c*(smalltrees[i-2][k]*table[i-1][j-1-k] // 左子树深度小于i-1table[i-1][k]*smalltrees[i-2][j-1-k] // 右子树深度小于i-1table[i-1][k]*table[i-1][j-1-k]);// 都为i-1table[i][j]%MOD;}for (int k0;kN;k) { // 确保接下来第i次迭代中的smalltrees[i-2][j]包含了深度小于i-1且节点数为j的树的个数smalltrees[i-1][k]table[i-1][k]smalltrees[i-2][k]; smalltrees[i-1][k]%MOD; }}fprintf (fout,%d\n,table[K][N]);return 0;
} 转载于:https://www.cnblogs.com/AbandonZHANG/archive/2012/07/19/2598501.html
