Time Limits: 2000 ms Memory Limits: 65536 KB

Description

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

Input

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

Output

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

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入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
2
3
4
5
6
7
8
输出1：
50.000000

输出2：
25.000000

输出3：
9.100000

Data Constraint

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 21
int n, m, sum[1 << N];
double g[N][N], f[1 << N];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            scanf("%d", &m);
            g[i][j] = m / 100.0;
        }
    f[0] = 1; sum[0] = 0;
    for (int s = 1; s < (1 << n); s++)
        for (int i = 1; i <= n; i++)
            if (s & (1 << i - 1)) {
                int last = s ^ (1 << i - 1);
                if (!sum[s]) sum[s] = sum[last] + 1;
                f[s] = max(f[s], f[last] * g[i][sum[s]]);
            }
    printf("%.6lf\n", f[(1 << n) - 1] * 100.0);
    return 0;
}