BZOJ5315 [JSOI2018]防禦網絡 【仙人掌 + dp】

題目連結

BZOJ5315

題解

題目好吓人= =點仙人掌 + 斯坦納樹

我們隻需求出對于所有選點的方案的斯坦納樹邊長總和

\(n\)那麼大當然不能狀壓，但是考慮一下如果這是一棵樹，一個方案的貢獻就是連接配接這些點的所有邊

我們可以考慮計算每條邊的貢獻

一條邊在樹上有貢獻，當且僅當它兩端的樹都存在被選擇的點

那麼這條邊\((u,v)\)貢獻就是

\[(2^{siz[u]} - 1)(2^{siz[v] - 1})

\]

其中\(siz[u]\)表示斷開這條邊後\(u\)一側的樹大小

如果放到仙人掌上呢？

對于割邊，和樹是一樣的

我們隻需計算每個環的貢獻

考慮我們對于一個環，選擇了其中\(K\)個點所在外向樹，那麼就有連接配接\(K\)個點的環上的\(K\)段邊，我們一定是除去最長那一條

是以我們斷環為鍊，設\(f[i][j][k]\)為選擇了區間\([i,j]\)的外向樹【意味着端點必選，中間不一定選，區間外一定不選】，\([i,j]\)中最大距離為\(k\)的方案數

那麼有，即考慮最後一段的長度

\[f[i][j][k] = (2^{siz[j]} - 1)(\sum\limits_{x = 0}^{k}f[i][j - k][x] + \sum\limits_{x = j - k + 1}^{j - 1}f[i][x][k])

直接轉移是\(O(n^4)\)的，常數很小資料很水可以跑過。。。

當然可以字首和優化成\(O(n^3)\)

【其實是我字首和寫炸了，直接交一波暴力轉移竟然\(A\)了。。。】