BZOJ

orz MilkyWay天天做sxt！

---

首先可以樹形DP：\(f[i][j][0/1]\)表示\(i\)個點的子樹中，黑高度為\(j\)，根節(jié)點為紅/黑節(jié)點的最小紅節(jié)點數(shù)（最大同理）。
轉(zhuǎn)移的時候枚舉兩棵子樹中有多少點、顏色是什么即可。
因為紅黑樹的深度是\(O(\log n)\)的，所以第二維只需要\(O(\log n)\)，所以復雜度是\(O(n^2\log n)\)。代碼這里有。

---

因為問題可以拆分成子問題，所以我們考慮幾種節(jié)點數(shù)較少的子樹的情況，然后把這棵子樹合并成一個黑點（表示一棵以該黑點為根的子樹）。
對于兩個黑點，我們可以把它合并成一個黑點。
對于三個黑點，可以合并成一個紅點與一個黑點。
對于四個黑點，可以合并成兩個紅點與一個黑點。
（看圖就很好理解了，盜用一下這位dalao的圖）

而且只需要考慮這三種情況。

初始的時候前端節(jié)點有\(n+1\)個，所以相當于把\(n+1\)個黑點合并至\(1\)個點。
大概也可以這么理解：因為將\(x\)個黑點合并成一個黑點，本質(zhì)上就是確定\(x-1\)個點選什么顏色。所以我們合并\(n+1\)個點就可以了。
求最小值就每次合并\(2\)個，當有奇數(shù)時是\(3\)個點，得補一個紅點。
求最大值就每次合并\(4\)個。因為實際上就是每次填\(1\)的深度，所以如果多余\(1\)個要與一個\(4\)拼成\(2\)和\(3\)，余下\(2\)個或\(3\)個可以直接單獨合并成\(1\)個。最后剩下兩個的時候特判下，根節(jié)點可以放紅點。

另外這樣高度限制沒有問題，剛開始是一層高度相同的前端節(jié)點，然后兩個兩個合并，高度都會\(+1\)（多出來就合并3個，高度也是\(+1\)）。
四個四個合并同理。

---

//820kb 0ms #include <cstdio>int main() {int n,ans=0; scanf("%d",&n);for(int x=n+1; x>1; x>>=1) ans+=x&1;printf("%d\n",ans), ans=0;for(int x=n+1; x>1; ){if(x==2) ++ans; switch(x&3){case 0: ans+=x>>1, x>>=2; break;// /4*2case 1: ans+=(x>>1)-1, x>>=2, ++x; break;// /4*2-1case 2: ans+=(x>>2)<<1, x>>=2, ++x; break;case 3: ans+=((x>>2)<<1)+1, x>>=2, ++x; break;}}printf("%d\n",ans);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/SovietPower/p/10512932.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ.3227.[SDOI2008]红黑树tree(树形DP 思路)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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