[USACO]Cow Pedigrees
嗯,好久没写过题解了啊...
首先我们定义:
- f[i,j]为i个结点,深度最大为j取得的树的数目
接着来一个证明:
- 对于每一棵度只为0或2的二叉树(完全二叉),结点总数肯定为奇数
证明如下:
- 令 n0表示度为0的结点,即叶子
- 令n1表示度为1的结点,显然在二叉树里为0
- 令n2表示度为2的结点,显然在二叉树里有: n2+1=n0
- 则结点总数n=n0+n1+n2=2*n0+1,显然n为奇数
- 得证
然后我们可以将一棵二叉树分为3部分:根,左儿子,右儿子,
设共有n个结点,根有1个,左儿子有i个,则右儿子有n-i-1个,
则可以得到这棵有n个结点,k层深的二叉树有f[i,k-1]*f[n-i-1,k-1]个结点,(乘法原理)
再配合加法原理可以得知:
- f[n,k]=Σ{f[i,k-1],f[n-i-1,k-1]|1≤i≤n-2 and i and 1=1}
接着得到边界条件:
- f[1,k]=1
最后答案就是
- f[n,k]-f[n,k-1] (注意<0)
为什么要这么减?看看f的定义是什么?
http://fayaa.com/code/view/14560/
真是一道好题目额~DP状态太多太神奇了......基本在2.3的题目都是靠看题解来想状态,很难做到独立构思一个完整的出来.
还有26天复赛了.