| 题目名称 | 725. [SDOI 2007] 科比的比赛 |
|---|---|
| 输入输出 | kobe.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 sywgz
于2012-04-01加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：0， 提交：0， 通过率：0% | |||
| 关于 科比的比赛 的近10条评论(全部评论) |
|---|
-
[试题描述]
NBA球星云集，谁是最厉害的呢？没有定论。
Nba总裁大卫*斯特恩最近闲得无聊，决定举办一场球员单挑大赛。
比赛是这样的:首先，我们给每人都打上个分数，表示了每个人的整体能力。然后让每个参赛队员都打n场比赛，首先看谁赢得最多，然后看谁打赢的人的能力值的和最大。
本人一向支持科比(我不支持),当然希望他赢。现在让我们和科比一起去赢得这场比赛吧！！
(科比照片一张)
假设总共比赛有m+1个人参加，告诉你科比和另外m个人的比赛的胜利可能性，你的任务就是求出在科比赢了的所有比赛的可能性最大的前提下(误差不超过1e-10)，科必打赢的人的最大能力值的和是多少？当然当一个人被你打败，他就不会再参加比赛了。
这里需要注意的是，科比能打赢其他人的可能性在不同场次是不同的。比如在比赛前期科比的手感不太好，对抗在内线称霸的人因为无法发挥外线的实力，而难以得分(接奥尼儿图一张)
中期时别人手感变好，状态起来，有实力的人会给科比制造很大的麻烦(接韦德图一张)
后期时消耗太多体力，对自己的命中率下降，难以发挥正常水平，所以对抗体力好的球员时占劣势(后接纳什图一张)
现在给你每场比赛科比对每个参赛者的获胜可能性，和每个人的能力值，帮助科比赢得比赛吧。
[输入]
第一行n,m(1<=n<<=10,n<=m<=100000),意义如题所述
接下来一行m个整数表示其他m个人的能力值si(1<=si<=100)
接下来是1个n*m的矩阵，描述在每场碰到每个人的获胜可能vij(0<=vij<=1)
[输出]
第一行输出最大获胜可能性
第二行输出最大能力值和
Special Judge
[样例]
kobe.in
3 4
91 92 93 94
0.5 0.5 0.5 0.5
0.5 0.5 0.5 0.5
0.5 0.5 0.5 0.5
kobe.out
0.125
279