UASCO Cow Pedigreesoj10140

题目大意：

输入n，m ；二叉树

输出 n个点分为m层 的方案数； 每个点的分支要么是0要么是2

Sample Input

5 3

Sample Output

2

即 两个方案为          O                     O         /   \                   /   \       O    O     和      O    O      /   \                          /   \    O    O                     O    O     关于  dp[ i ][ j ] = dp[ i ][ j ] + dp[ i-1-k ][ j-1 ] * dp[ k ][ j-1 ]   可以这样理解，i 个点分为 j 层时 先取出一个点做根节点为第一层 剩下 i-1 个点则分为左右两大支 则此时 i-1 个点被分为两大支，且每支应分为 j-1 层  则 （i-1-k 分为 j-1 层的方案）*（k 分为 j-1 层的方案）= i 分为 j 层的方案         #include <bits/stdc++.h> #define MOD 9901 using namespace std; int dp[210][110]; int main() { int n,m; while(~scanf("%d%d",&n,&m)) { memset(dp,0,sizeof(dp)); for(int j=1;j<=m;j++) for(int i=1;i<=n;i+=2) { if(i==1) dp[i][j]=1; for(int k=1;k<=i-2;k+=2) dp[i][j]=(dp[i][j]+dp[i-1-k][j-1]*dp[k][j-1])%MOD; } printf("%d\n",(dp[n][m]-dp[n][m-1]+MOD)%MOD); } return 0; } View Code

 

转载于:https://www.cnblogs.com/zquzjx/p/9053750.html

相关资源：JAVA上百实例源码以及开源项目