洛谷P3577【[POI2014]TUR

洛谷P3577【[POI2014]TUR"/>

洛谷P3577【[POI2014]TUR

Here
此题做法：状压DP

f [ d ] [ s ] f[d][s] f[d][s]表示深度为d时，当前节点及其祖先状态为s是，以该节点为根的子树及其祖先的最小费用和。

由于任意两点之间的简单路径不超过十个点因此可以状态压缩。

其中s的（从左往右）第一位表示该点状态，第二位表示该点的父亲节点的状态，第三位表示爷爷，以此类推。

此处需要的时三进制状态，因为共有三种状态。0表示该点建立了旅游站点，1表示该点没有建旅游站点且没有被覆盖，2表示该点没有建旅游站点但被覆盖。

那么转移方程深思熟虑一下~~~可以得出

若该点不建旅游站点那么 如果该点被覆盖那么

f [ d ] [ s + 2 ∗ p o w [ d ] ] = m i n ( f [ d ] [ s + 2 ∗ p o w [ d ] , f [ d − 1 ] [ s ] ) f[d][s + 2 * pow[d]] = min(f[d][s + 2 * pow[d],f[d - 1][s]) f[d][s+2∗pow[d]]=min(f[d][s+2∗pow[d],f[d−1][s])

否则如果该点没有被覆盖那么

f [ d ] [ s + p o w [ d ] ] = m i n ( f [ d ] [ s + p o w [ d ] , f [ d − 1 ] [ s ] ) f[d][s + pow[d]] = min(f[d][s + pow[d],f[d - 1][s]) f[d][s+pow[d]]=min(f[d][s+pow[d]