集合型DP

集合型动态规划

如何用一个数表示集合?

bitset:用一个二进制数

$\cup$:s1 | s2
$\cap$:s1 & s2

查询是否有第i位:(1<<i) & s

补集:((1<<n)-1) ^ s

最优配对问题


题目

空间里有2n个点,将它们配成n对,使得每对距离之和最小, n <= 10

分析

  • dp[s]=min(dp[s],dis[i][k]+dp[s^t^(1<<k)])
# DP, 笔记

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×