首页 > 其他 > 详细

JZOJ 1236. 邦德I

时间:2019-08-10 22:28:19      阅读:102      评论:0      收藏:0      [点我收藏+]

题目

Description

每个人都知道詹姆斯邦德,著名的007,但很少有人知道很多任务都不是他亲自完成的,而是由他的堂弟们吉米邦德完成(他有很多堂弟),詹姆斯已经厌倦了把一个个任务分配给一个个吉米,他向你求助。
每个月,詹姆斯都会收到一些任务,根据他以前执行任务的经验,他计算出了每个吉米完成每个任务的成功率,要求每个任务必须分配给不同的人去完成,每个人只能完成一个任务。
请你编写程序找到一个分配方案使得所有任务都成功完成的概率。
 

Input

输入第一行包含一个整数N,表示吉米邦德的数量以及任务的数量(正好相等,1<=N<=20)。
接下来N行,每行包含N个0到100之间整数,第i行的第j个数Aij表示吉米邦德i完成任务j成功的概率为Aij%

Output

输出所有任务成功完成最大的概率,结果保留6位小数。
 

Sample Input

输入1:
2 
100 100 
50 50 

输入2:
2 
0 50 
50 0 

输入3:
3 
25 60 100 
13 0 50 
12 70 90 

Sample Output

输出1:
50.000000

输出2:
25.000000

输出3:
9.100000
 

Data Constraint

 

分析

 

  • 状压设f[s]为前i个人的情况为s

 

代码

 

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 double f[1<<21];
 5 double a[100][100];
 6 int main ()
 7 {
 8     int n;
 9     cin>>n;
10     for (int i=1;i<=n;i++)
11       for (int j=1;j<=n;j++)
12         cin>>a[i][j],a[i][j]/=100;
13     int maxn=(1<<n)-1;
14     f[0]=1;
15     for (int i=0;i<=maxn;i++)
16     {
17         int x=__builtin_popcount(i);
18         for (int j=1;j<=n;j++)
19         {
20             if (x==j-1)
21             {
22                 for (int k=1;k<=n;k++)
23                 if (!(i&(1<<(k-1))))
24                 {
25                      f[i|(1<<(k-1))]=max(f[i|(1<<(k-1))],f[i]*a[j][k]);
26                 }
27             }
28         }
29     }
30     printf("%0.6lf",f[maxn]*100);
31 }

 

JZOJ 1236. 邦德I

原文:https://www.cnblogs.com/zjzjzj/p/11333046.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!