题目大意
对于所有的整数\(k \in [1,n]\)，求叶子结点有\(k\)个的二叉树个数，满足每个非叶子结点都有两个儿子，并且对于每个叶子结点，从根节点到它经过的向左的边数少于等于\(m\)个。
思考历程
很容易推出这样的\(DP\)：
设\(f_{i,j}\)表示\(m=i\)且\(n=j\)的答案是多少。\(f_{i,j}=\sum_{k \in [1,n)}{f_{i-1,k}f_{i,j-k}}\) 这样当然过不了。 然而，如果只看第二维，就会感觉它和卡特兰数长得很像。 于是就往打表的方面想…… 打出一个表，表可以分成上下两个三角形，下面的那个三角形就是标准的卡特兰数…… 然而找不到上面的规律。 %%%GMH大佬居然找到了。 于是就暴力了……正解
换一种思路\(DP\)：
设\(f_{i,j}\)表示已经放了\(i\)个节点，从根往下走已经向左走了\(j\)次。 有两种转移： 一个是继续向左走，那就是转移到\(f_{i+1,j+1}\) 另一个是回到第一个左转的地方，放一个右儿子，那就是转移到\(f_{i+1,j-1}\) 很显然放的节点个数为\(2k-1\)，所以这个方法是能过的。代码
using namespace std;#include#include #include #define N 5010#define mo 998244353#define ll long longint m,n;ll f[N*2][N];int main(){ freopen("ca.in","r",stdin); freopen("ca.out","w",stdout); scanf("%d%d",&m,&n); f[1][0]=1; for (int i=1;i<2*n-1;++i) for (int j=0;j
总结
在做树一类的\(DP\)的时候，不要仅仅是想着从下往上转移，还要考虑一下按照\(dfs\)序来转移。