HDU5045-Contest(DP+狀態壓縮)
來源：程序員人生 發布時間：2014-10-17 05:29:17 閱讀次數：1921次
題目鏈接
題意：有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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
