題目：http://www.nocow.cn/index.php/Translate:USACO/nocows

?

題意：給定n個節(jié)點，求形成高度為k且出度只能為0或2的二叉樹的個數(shù)。

?

分析：我們用dp[n][k]來表示n個節(jié)點深度為k的上述二叉樹的個數(shù)。很明顯，如果n為偶數(shù)，那么dp[n][k]=0，所以我們只

考慮n為奇數(shù)的情況。

?

#include <iostream> #include <string.h> #include <stdio.h>using namespace std; const int MOD = 9901; const int N = 204; const int M = 105;int dp[N][M]; int f[N][M];void Init() {memset(dp,0,sizeof(dp));memset(f,0,sizeof(f));dp[1][1] = 1;for(int k=1;k<M;k++)f[1][k] = 1;for(int k=2;k<M;k++){for(int i=3;i<N;i+=2){int sum = 0;for(int j=0;j<=i-2;j++)sum = (sum + dp[j][k-1]%MOD*(f[i-1-j][k-2]%MOD*2 + dp[i-1-j][k-1]%MOD))%MOD;dp[i][k] = sum;f[i][k] = (f[i][k-1]%MOD + dp[i][k]%MOD)%MOD;}} }int main() {int n,k;Init();while(cin>>n>>k)cout<<dp[n][k]<<endl;return 0; }

?

?

總結(jié)

以上是生活随笔為你收集整理的高度为k的二叉树个数(递推分析)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。