Lightoj 1011 Marriage Ceremonies

admin · 发表于 2018-8-24 15:56:59

题意：给你n*n的矩阵，a[i][j]代表第i个男人和第j个女人之间的满意度，求男女一一配对后，最大的满意度之和。(n<=16)

admin · 发表于 2018-8-24 15:57:08

思路:可以直接套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])

		自动登录	找回密码
密码			立即注册