自动搬运

查看原文

来自洛谷，原作者为

	crpboy 还是太菜了

搬运于2025-08-24 21:59:03，当前版本为作者最后更新于2019-04-18 09:09:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

状压dp套路题。

$n$的范围很小，考虑状压dp。我们设$f[i]$表示选择的任务状态为$i$的时候的最大的成功率。

枚举任务$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;
}