Codeforces Round#9(Div2 only) D. How many trees?
今日はPKUちゃんと解かないと。。。
問題概要
要素数がn個、高さがh以上の二分探索木がいくつあるか求めよ。
ただしここでいう二分探索木とは、
- 各頂点には1以上n以下のそれぞれ異なる整数が書かれている
- 各頂点は0個以上2個以下の子を持ち、左側の子の頂点に書かれている数字は全て親の頂点に書かれている数字より小さく、右側の子の頂点に書かれている数字は全て親の頂点に書かれている数字より大きい
のようなものをいい、二分探索木の高さとは、根から最も遠い葉までの距離(両端も含む)のことを言うものとする。
n, h≦35であり答えは9*10^18以下であることが保証されている。
以下解法とソースコード。
解法
まずは高さ制限のない二分探索木の総数を求めることを考える。例えばn=10.
根の数字をi=4などと決めると、
- それより左側の部分の数字は1から3(すなわちi-1個)
- それより右側の部分の数字は5から10(n-i個)
である。ここで、それぞれのグラフがまた二分探索木になっていることに注目すれば再帰が使えることに気づくはず。
右側の木は各数字が5から10であるが、グラフの総数としてはn=6のものと変わらないことに注意。
次に高さ制限のある木を考える。
上の場合において再帰関数に高さの情報を持たせたいが、「高さがh以上」よりも「高さがh以下」のほうが計算しやすい。
「高さがh以上」の方針だと、ある頂点を決めると、
- それより左側が高さ0以上で右側が高さh-1以上
- 左側が高さh-1以上で右側が高さ0以上
- 両側が高さh-1以上
の場合〜などと場合分けしなければならないが(それでも多分できる)、高さh以下ならば
- 左側の高さも右側の高さもh-1以下
とだけ条件をつければ良いからである。
ある高さ以下の木が求められれば(全ての高さの木の数)-(h-1以下の高さの木の数)が問題の(h以上の高さの木の数)となる。
あとはオーバーフローなどに気をつけてメモ化再帰を実装する。
ソースコード
ll memo[36][36]; ll calc(int n,int h) { if(n>0&&h==0)return 0; if(n==0)return 1; if(memo[n][h]>=0)return memo[n][h]; ll ret=0; for(int i=1;i<=n;i++) { ret+=calc(i-1,h-1)*calc(n-i,h-1); } return memo[n][h]=ret; } void run() { int n,h; cin>>n>>h; rep(i,36)fill(memo[i],memo[i]+36,-1); cout<<calc(n,n)-calc(n,h-1)<<endl; }