因为数据规模的问题(N<=10,M<=10000),给人的第一感觉会是集合DP.但是集合DP是O(M*N*2^N)的时间复杂度,是超时的.然后我们会想到KM匹配,但是边数为10000*10,显然还是很大……细细地看一下题目,N的规模非常小,M的规模非常大.那么,我们很容易想到缩小M的规模.因为对于sempr的每一个人物来说,他只可能匹配到styc的M个人物中的对他胜率最大的N个人物中的一个,所以styc的每个人物只需要向外连接N条边就可以了,这样,如果顶点不重复,那么最多就是N*N个点,那么就是N个点和N*N个点做KM匹配,因为N很小,所以很容易解决.对于解决乘法，可以把所有的边log一下，最后再exp即可。当然了，一种更快的做法就是：首先排序，sempr的每个人物选择10个对他胜率最大的，然后变成了一个10×100的图，然后做一下集合DP。

• 感谢flymouse牛对比赛的后期支持…… (0) byron 2007-01-01 23:50:03
• 集合的DP怎么搞？ (18) bmexue 2007-01-04 17:30:45
  • 100×10的矩阵……然后每列抽取一个数字，不在同一行。。。乘起来最大。。。这不狠easy么 (20) flymouse 2007-01-04 17:39:12
    • 这题有用匹配过的吗？我的总是超时，不过也可能是我的KM写成O（N^4）的了>_< (0) byron 2007-01-04 18:17:59
    • Re:100×10的矩阵……然后每列抽取一个数字，不在同一行。。。乘起来最大。。。这不狠easy么 (19) bmexue 2007-01-04 18:37:50
      • 这样做就是超时了，我试了 (23) bmexue 2007-01-04 20:35:43
        • 好郁闷，改集合DP吧……sigh…… (0) byron 2007-01-04 22:55:48
          • Re:好郁闷，改集合DP吧……sigh…… (0) fzszjs1z 2007-01-08 22:11:26
            • 为什么会 run time error (4414) fzszjs1z 2007-01-08 22:13:55
          • 更正一下，KM可过，是我写得太搓了，所以至今没过…… (15) byron 2007-01-09 23:09:13
            • Re:更正一下，KM可过，是我写得太搓了，所以至今没过…… (18) byron 2007-01-11 17:59:37
• 没看题目,单看解释就觉得很帅 Orz (384) ziliang 2007-01-04 22:56:10