洛谷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]
更多推荐
洛谷P3577【[POI2014]TUR
发布评论