做鞋子出口需要作网站吗/国内最新十大新闻

这个数据，很明显的状压dp。

我们令 dp[s]为当前状态为s，1获胜的最大概率。二进制01代表死没死。

怎么转移呢？枚举两个不同的人取max。

AC代码：

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=19;
int n;
double p[N][N],dp[1<<N];
signed main(){cin>>n;	dp[1]=1.0;for(int i=0;i<n;i++)	for(int j=0;j<n;j++)	cin>>p[i][j];for(int s=2;s<(1<<n);s++)for(int i=0;i<n;i++)	if(s>>i&1)for(int j=i+1;j<n;j++)	if(s>>j&1)dp[s]=max(dp[s],dp[s^(1<<i)]*p[j][i]+dp[s^(1<<j)]*p[i][j]);printf("%.10lf\n",dp[(1<<n)-1]);return 0;
}