题目意思
从 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)])
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
正确代码