题解
二进制dp
etc: 令 \(dp[00110]\) 代表前两个任务选23两个人出战的最大成功率 则 \(dp[00110]=max(dp[00010]+a[3][2],dp[00100]+a[2][3])\)
code
#include<bits/stdc++.h>
using namespace std;
double a[25][25]={0};
double dp[1<<22]={0};
int cal(int now)
{
int sum=0;
while(now)
{
sum+=now%2;
now/=2;
}
return sum;
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>a[i][j];
a[i][j]/=100.0;
}
}
dp[0]=1;
for(int i=1;i<(1<<n);i++)
{
int num=cal(i);
for(int j=0;j<n;j++)
{
if((i>>j)&1) dp[i]=max(dp[i],dp[i^(1<<j)]*a[j+1][num]);
}
}
printf("%.6lf\n",dp[(1<<n)-1]*100.00);
return 0;
}
标签:25,int,max,COCI2006,P4329,00110,2007,dp
From: https://www.cnblogs.com/pure4knowledge/p/18115790