acgo题库
  • 首页
  • 题库
  • 学习
  • 天梯
  • 备赛

    竞赛

    • CSP-J/S
    • 蓝桥杯

    考级

    • GESP
    • CPA
    • 电子学会考级
  • 竞赛
  • 讨论
  • 团队
  • 商城
登录
注册
题目详情提交记录(0)
  • T23:General Weighted

    题目意思 从 N 个点中选若干条边,要求选到的边两两不共用端点(匹配)。求这些边的长度和的最大值。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 思路解析 用二进制 mask 表示一个点集(哪些点参与考虑)。 * dp[mask]:只在 mask 这批点里面选边,能得到的最大总长度。 * 基础:如果 mask 里只有两个点 u,v,那么 dp[mask] = D[u][v](只选这一条边)。 * 转移:对一个偶数个点的 mask,任选两点 u,v 配成一条边,剩余部分继续最优: * dp[mask] = max(dp[mask], dp[mask^(1<<u)^(1<<v)] + dp[(1<<u)|(1<<v)]) * 最终答案: * 如果 N 是偶数,答案是 dp[ALL] * 如果 N 是奇数,可以去掉任意一个点不参与:答案是 max(dp[ALL^(1<<i)]) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 正确代码

    userId_undefined
    知予
    倔强青铜
    2阅读
    0回复
    0点赞
暂无数据

提交答案之后,这里将显示提交结果~

首页