CodeForces - 16E（状压dp）

const int maxn = 5e4 + 10;
double dp[1 << 18];
int num[1 << 18];
double pic[20][20];
int sta[20][maxn], cnt[20];

int lowbit(int x) {
	return (x & (-x));
}

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			scanf("%lf", &pic[i][j]);

	int limit = (1 << n);
	
	for (int i = 1; i < limit; ++i)	num[i] = num[i - lowbit(i)] + 1;

	for (int i = 0; i < limit; ++i) {//预处理出不同种1个数的状态
		int temp = num[i];
		sta[temp][cnt[temp] ++] = i;
	}

	dp[limit - 1] = 1;
	for (int i = n-1; i >= 1; --i) {//剩余的鱼条数
		for (int j = 0; j < cnt[i]; ++j) {
			int now = sta[i][j];//当前状态
			for (int k = 0; k < n; ++ k) {//添个1
				int pre = (now | (1 << k));
				if (pre == now)	continue;
				int c = (i * (i + 1)) / 2;//C(i+1, 2), 即两条鱼中间偶遇的可能
				for(int z = 0; z < n; ++ z)
					if((1 << z) & pre)	dp[now] += dp[pre] * pic[z][k] / c;
			}
		}
	}

	for (int i = 1; i < limit; i <<= 1)
		printf("%.6lf%c", dp[i], i == limit - 1 ? ‘\n‘ : ‘ ‘);
	
	return 0;
}

CodeForces - 16E（状压dp）

原文：https://www.cnblogs.com/wanshe-li/p/13787617.html