HDU5045-Contest(DP+状态压缩)
来源：程序员人生 发布时间：2014-10-17 05:29:17 阅读次数：1788次
题目链接
题意：有n个人做m道题目，每个人对于每题都有答对的概率，求最后答出所有题目概率的最大值。有要求就是每两个人之间答题的数目不能超过1。
思路：DP+状态压缩。dp[i][j]表示前i道题目j个人答题状态的最大值，j用二进制表示，因为人最多就10个。因为每两个人之间答题数目不能超过1，所以当状态达到1 << n - 1，即所有人都答过一题时，将重置为0。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1200;
double p[15][MAXN];
double d[MAXN][MAXN];
int n, m;
void dp() {
for (int i = 0; i <= m; i++)
for (int j = 0; j < (1 << n); j++)
d[i][j] = -1.0;
d[0][0] = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < (1 << n); j++) {
if (d[i][j] < 0) continue;
int st;
for (int k = 0; k < n; k++) {
if (!((1 << k) & j)) {
st = j | (1 << k);
if (st == (1 << n) - 1)
st = 0;
d[i + 1][st] = max(d[i + 1][st], d[i][j] + p[k][i]);
}
}
}
}
int main() {
int cas, t = 1;
scanf("%d", &cas);
while (cas--) {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
scanf("%lf", &p[i][j]);
dp();
double ans = 0;
for (int i = 0; i < (1 << n); i++)
ans = max(ans, d[m][i]);
printf("Case #%d: %.5lf
", t++, ans);
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
