HDU 5045 Contest 期望+狀壓dp 2014 ACM/ICPC Asia Regional Shanghai Online
來源：程序員人生 發布時間：2014-09-30 00:02:23 閱讀次數：2363次
題意：
給定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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
