526互联
首页
Ai
Java
Python
Android
Mysql
JavaScript
Html
CSS
P8352
P8352 [SDOI/SXOI2022] 小 N 的独立集
经典最大独立集问题可设 \(dp_{u,0/1}\) 表示 \(u\) 为根的子树内,不选/选 \(u\) 的独立集最大权。 本题求方案数,且 \(k\) 这么小,暗示我们将上面状态压到维度,设 \(f_{u,i,j}\) 表示以 \(u\) 为根的子树内,\(dp_{u,0}=i,dp_{u,1} ......
P8352
8352
2022
SDOI
SXOI
更新时间 2023-10-28
P8352 [SDOI/SXOI2022] 小 N 的独立集
碎碎念 不会写难题,随简单省选题切一切捏。 注意到,一定是要钦定所有的 nk 种权值之后再去算方案的。 对于最大权独立集,我们可以设。 dp[x][0/1][v] 表示 x 选/不选,其子树内已经选了权值 v 作为其最大独立集的方案数。 就是这个捏。 需要注意的是,如何处理所钦定的 v 统计的方案一 ......
P8352
8352
2022
SDOI
SXOI
更新时间 2023-03-24
共2篇 :1/1页
首页
上一页
1
下一页
尾页