HDU5045-Contest(DP+狀態壓縮)

HDU5045-Contest(DP+狀態壓縮)

題目鏈接

題意：有n個人做m道題目，每個人對於每題都有答對的概率，求最後答出所有題目概率的最大值。有要求就是每兩個人之間答題的數目不能超過1。

思路：DP+狀態壓縮。dp[i][j]表示前i道題目j個人答題狀態的最大值，j用二進制表示，因為人最多就10個。因為每兩個人之間答題數目不能超過1，所以當狀態達到1 << n - 1，即所有人都答過一題時，將重置為0。

代碼：

#include 
#include 
#include 
#include 

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\n", t++, ans);
    }
    return 0;
}