Codeforces 678E 状压DP

题意：有n位选手，已知n位选手之间两两获胜的概率，问主角(第一个选手）最终站在擂台上的概率是多少？

思路：一看数据范围肯定是状压DP，不过虽然是概率DP，但是需要倒着推；我们如果正着推式子的话，初始状态是不确定的，因为并不知道一开始把哪个人放在擂台上最后主角获胜的概率最大。所以我们可以假设主角最后获胜的概率是1，然后倒着推。设dp[i][j]表示现在站在擂台上的是i号选手，状态是j，主角获胜的最大概率，其中状态j的k位置是1代表第k - 1个选手还没有被淘汰。所以dp[i][j] = max(dp[i][j ^ (1 << k)] * a[i][k] + dp[k][j * (1 << i)] * a[k][i]).代表的决策是：现在站在擂台上的人是i,如果k去挑战有2种情况：1，k获胜了，那么转移到dp[k][j * (1 << i)], 转移概率是a[k][j]，k失败了同理。那么在当前状态选择k去挑战擂台的获胜的总概率是两种可能获胜概率的总和。

代码：

#include <bits/stdc++.h>

#define db double

using namespace std;

const int maxn = 100010;

db dp[18][1 << 18];

db a[18][18];

int main() {

	int n;

	scanf("%d", &n);

	for (int i = 0; i < n; i++)

		for (int j = 0; j < n; j++)

			scanf("%lf", &a[i][j]);

	dp[0][1] = 1;

	for (int i = 1; i < (1 << n); i++) {

		for (int j = 0; j < n; j++) {

			if((i >> j) & 1) {

				for (int k = 0; k < n; k++) {

					if(k == j) continue;

					if((i >> k) & 1) {

						dp[j][i] = max(dp[j][i], dp[k][i ^ (1 << j)] * a[k][j] + dp[j][i ^ (1 << k)] * a[j][k]);

					}

				}

			}

		}

	}

	db ans = 0;

	for (int i = 0; i < n; i++)

		ans = max(ans, dp[i][(1 << n) - 1]);

	printf("%.7lf\n", ans);

}

巴特西

Codeforces 678E 状压DP

最新文章

热门文章