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\)了。。。】