1603?限高二叉排列樹 題目來源：?CodeForces 基準時間限制：1?秒 空間限制：131072?KB 分值:?40?難度：4級算法題

作為游戲魔方的編寫者和管理員，Bob在很多主存模塊中檢測游戲魔方，并且Bob從未被用戶打敗，同時他也經常和游戲魔方作戰。

然而，不愉快的事情發生了，游戲《失落的洛杉磯》崩潰了，由于出現了一個非常可惡的病毒——“十六進制”，它非常奇怪，并且非常喜歡玩，因此，Bob必須先和它玩，才能和別人玩。

此次“十六進制”發明了以下游戲：Bob必須通過一些有n個節點的二叉搜索樹，二叉搜索樹是一顆二叉樹，每個節點有一個唯一的關鍵字。我們來說一下二叉搜索樹的性質，以下規則在每個節點上都成立：每個節點的關鍵字都大于左子樹上的所有節點的關鍵字，都小于右子樹上所有節點的關鍵字。每個關鍵字都是從1~n的不同的正整數。每棵樹上的所有節點都最多有兩個子節點，或者沒有子節點（在這種情況下的節點被稱為葉子節點）。

在“十六進制”的游戲中，所有的樹都是不同的，但是每棵樹的高度都不低于h。在此問題中，“高度”指的是從根節點到最遠的葉子節點的最多節點數（包含葉子節點和根節點）。當Bob跳過一棵樹的后，這棵樹會消失。當所有的樹都消失了，Bob就通過了游戲魔方。他想知道在最壞的情況下，他必須跳過多少棵樹，你能幫助他嗎？

Input 單組測試數據 輸入數據包含兩個以空格隔開的正整數n和h?(1<=n<=35,1<=h<=?n)?。 Output 輸出一個整數表示問題的答案。題目保證這個整數不超過9*10^18。 Input示例 3?2 Output示例 5


//對于DP還是不夠強啊，想到一部分，但還是沒有找到狀態方程
按理說，性質很容易發現，二叉搜索樹，如果根節點確定，那么，左右樹的節點數就一定了
然而我想的是dp[i][j]為根為 i ，j 高度的種數，然后思索了半天，發現并不好dp，唉
假如 dp[i][j] 是 i 個節點，高度小于等于 j 的個數的話，就非常好做了、、、
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 #define LL long long 5 #define eps 1e-8 6 #define MX 40 7 8 int n,h; 9 LL dp[MX][MX]; 10 11 int main() 12 { 13 while (scanf("%d%d",&n,&h)!=EOF) 14 { 15 memset(dp,0,sizeof(dp)); 16 for (int i=0;i<=n;i++) 17 dp[0][i]=1; 18 for (int i=1;i<=n;i++) 19 for (int j=1;j<=n;j++) 20 for (int k=1;k<=i;k++) 21 dp[i][j]+=dp[k-1][j-1]*dp[i-k][j-1]; 22 printf("%lld\n",dp[n][n]-dp[n][h-1]); 23 } 24 return 0; 25 } View Code

?

轉載于:https://www.cnblogs.com/haoabcd2010/p/7545033.html

總結

以上是生活随笔為你收集整理的1603 限高二叉排列树(计数DP)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。