team2012-D1-sol-0026

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

这种类型的问题, 首先有一个结论就是一共有N个项目, 每个项目的备选人留前N个最优的就可以了, 其他人都是没用的... 所以可以把M的范围缩小到N*N, 这道题里N=10, 所以M的范围可以缩小到100. 然后就可以做了. 用带权最大匹配和DP两种做法都行. 注意用匹配来做的话, 这题的权值是一个双关键字, 所以需要自己写类重载一下运算符, 方便使用模版, 另外不了解匹配算法的话可能会改不来. 另外一种算法是DP, 这个没什么好说的, 经典的背包问题. 时间复杂度: O(2^n^*n^3^). (此题里n=10)

这种类型的问题, 首先有一个结论就是一共有N个项目, 每个项目的备选人留前N个最优的就可以了, 其他人都是没用的... 所以可以把M的范围缩小到N*N, 这道题里N=10, 所以M的范围可以缩小到100. 然后就可以做了. 用带权最大匹配和DP两种做法都行. 注意用匹配来做的话, 这题的权值是一个双关键字, 所以需要自己写类重载一下运算符, 方便使用模版, 另外不了解匹配算法的话可能会改不来. 另外一种算法是DP, 这个没什么好说的, 经典的背包问题. 时间复杂度: O(2ⁿ*n³). (此题里n=10)