华师一附中OI组

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 1278|回复: 1
打印 上一主题 下一主题

Lightoj 1011 Marriage Ceremonies

[复制链接]

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
跳转到指定楼层
楼主
发表于 2018-8-24 15:56:59 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
题意:给你n*n的矩阵,a[i][j]代表第i个男人和第j个女人之间的满意度,求男女一一配对后,最大的满意度之和。(n<=16)

回复

使用道具 举报

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
沙发
 楼主| 发表于 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])
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|服务支持:DZ动力|华师一附中OI组  

GMT+8, 2024-12-26 02:04 , Processed in 0.790478 second(s), 23 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表