题解 P4329 【[COCI2006-2007#1] Bond】

· · 题解

状压dp套路题。

枚举任务$j$，如果当前状态$i$第$j$位已经选过，就从没选$j$的状态转移。 转移方程 $$\large f[i]=max\{f[i\ xor\ 2^{j-1})]\times a[cnt(i)][j]\}$$ （$cnt$表示$i$中$1$的个数） 初始$f[0]=1$，答案$f[2^n-1]

如何确定是哪个人选择任务？i二进制下的1的个数，就表示当前完成的任务个数。因此完成任务的人就可以顺序选择了。

时间复杂度O(n\times2^n)

upd: 删去了一些废话

AC代码

#include<bits/stdc++.h>
using namespace std;
int n;
double a[25][25];
double f[(1<<20)+5];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%lf",&a[i][j]),a[i][j]*=0.01;
    int tot=1<<n;
    f[0]=1;//初始状态
    for(int i=0;i<tot;i++)
    {
        int x=i,cnt=0;
        for(;x;x>>=1)if(x&1)cnt++;//统计1个数
        for(int j=1;j<=n;j++)
            if(i&(1<<(j-1)))
                f[i]=max(f[i],f[i^(1<<(j-1))]*a[cnt][j]);//从没有选第j个任务的状态转移
    }
    printf("%.6lf",f[tot-1]*100);
    return 0;
}