华师一附中OI组

标题: Lightoj 1011 Marriage Ceremonies [打印本页]

作者: admin 时间: 2018-8-24 15:56
标题: Lightoj 1011 Marriage Ceremonies
题意：给你n*n的矩阵，a[i][j]代表第i个男人和第j个女人之间的满意度，求男女一一配对后，最大的满意度之和。(n<=16)

作者: admin 时间: 2018-8-24 15:57
思路:可以直接套KM板子，n^3复杂度，因为n比较小，也可以用状压做，n^2*2^n复杂度

转移方程：dp[i][sta|(1<<j)] = max(dp[i][sta|(1<<j)], dp[i-1][sta]+a[i][j])

欢迎光临华师一附中OI组 (http://hsyit.cn/)