CSP 201909-5 城市规划

正文索引 [隐藏]

这题感觉很迷幻……
CSP 现场的时候按照 70 分写了个 DP,对拍了 1 个小时交上去只有 20 分。现在想起来,重写了一遍,直接就 100 了。
我觉得 CSP 201909 这一场比赛的问题很大。第三题题意严重不清楚,第四题和第五题的数据我认为都有锅。

题目大意

给你一颗有 n 个点的树,其中 M 个点是重要点。要你从重要点中选择 K 个出来,使得任意两个被选择的重要点之间的距离和最小。问题要求这个最小的距离和。

题解

写了一个 O(nK^2) 的 DP,理论上来说对于最后的三个点应该会超时,然而并没有……

DP[x][k] 表示以 x 为根的子树内选择 k 个重要点对答案的最小贡献。最小贡献可以理解为,最终答案任意两点之间的距离在以 x 为根的子树内的这部分的距离之和。

转移方程就很简单,与 01 背包类似:对于 x 的任意子节点 v 都执行一遍 dp[x][k] = min(dp[x][k], dp[v][k^1] + dp[x][k – k^1]),注意这里的 k 需要从大往小枚举,以保证不会重复计算(01 背包与无限背包的区别)。

代码