首页 > [JLOI/SHOI2016]侦察守卫
开通博客写题解
头像 __故人__
发表于 2020-12-03 19:51:55
分析 比较奥秘重重的 状态设计。定义 为覆盖以 为根的全部子树，而且向上覆盖了 层节点。 表示，覆盖了以 为根，子树节点深度 的全部节点。 初始化 对于任何情况 。选择这个节点的转移。 如果当前点是关键点，那么 。由于必须要覆盖这个节点，那么初始化为必选状态。 如果当前点不是关 展开全文
去ta的博客 赞 (7) 回复(0) 收起
头像 BNDSBilly
发表于 2020-12-14 16:00:12
我们设计状态 g[i][j]表示当前在i节点，处理到了第k棵子树时，还能向外扩展j层的最小花费。 f[i][j]表示当前在i节点，处理到了第k棵子树时，在i节点的子树中向下还有j层没有被覆盖时的最小花费。 那么状态转移(现在在点u,v为新子树)： g[u][j]=min(g[u][j]+f[v][j 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”