洛谷4329 [COCI2006-2007#1] Bond

题意

有 $N$ 个人去执行 $N$ 个任务，每个人执行每个任务有不同的成功率，每个人只能执行一个任务，求所有任务都执行的总的成功率。（直接用题面）

$N\le 20$ 。

题解

用 $f[i]$ 表示任务完成状态为 $i$ 时的最大成功率。预处理出 $1$ 的个数 $cnt[i]$ ，枚举任务 $j$ ，很容易得到方程：

$$f[i]=\max f[i \ xor \ 2^{j-1} ]+s[cnt[i]][j]$$

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

int n,cnt[1048576];
double s[25][25],f[1048576];

signed main()
{
    n=read();
    const int N=1<<n;
    for (int i=0;i<N;i++) for (int j=i;j;j&=j-1) cnt[i]++;
    for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) s[i][j]=0.01*read();
    memset(f,-0x3f,sizeof(f)); f[0]=1;
    for (int i=1;i<N;i++)
    {
        for (int j=0;j<n;j++)
        {
            if (!(i>>j&1)) continue;
            int k=i^(1<<j);
            f[i]=max(f[i],f[k]*s[cnt[i]][j+1]);
        }
    }
    return !printf("%.6f",f[N-1]*100);
}