HDU 5045 Contest 期望+状压dp 2014 ACM/ICPC Asia Regional Shanghai Online
来源：程序员人生 发布时间：2014-09-30 00:02:23 阅读次数：2201次
题意：
给定n个人 m个题目
下面n*m的矩阵表示每个人解出每道题的概率
我们可以得到一个模长为m的集合{1,2,3,1,2}
代表每道题是谁解出的。
有众多集合，且获得这个集合有一个期望，求期望最大的那个集合 （ 的期望值是多少）
一个限制: 对于集合 {1,1,2,3,1} 这样是不合法的（即从[1,n]题必须是1-n的排列，然后[n+1, 2n]题也是一个排列）
然后状压dp
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int M= 1000 +2;
const int N= 10+2;
const int S= (1 << 10) + 10;
double d[M][S], p[N][M];
int main() {
int cas, mx, n, m, to;
scanf("%d", &cas);
for(int T= 1; T<= cas; ++T) {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
scanf("%lf", &p[i][j]);
mx = (1 << n) - 1;
memset(d, 0, sizeof d);
d[0][0] = 0;
for (int i = 0; i < m; ++i) {
int s = (1 << (i % n)) - 1;
while (s < mx) {
int x = s & -s;
int y = s + x;
for (int k = 0; k < n; ++k)
if (!(s >> k & 1)) {
to = s | (1 << k);
if (to == mx)
to = 0;
d[i + 1][to] = max(d[i + 1][to], d[i][s] * (1.0 - p[k][i]) + (d[i][s] + 1) * p[k][i]);
}
if (s == 0) break;
s = ((s & ~y) / x >> 1) | y;
}
}
double ans = 0;
for (int i = 0; i < mx; ++i)
ans = max(ans, d[m][i]);
printf("Case #%d: %.5f
", T, ans);
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
