HDU5045Contest(記憶化搜索)

HDU5045Contest(記憶化搜索)

HDU5045Contest(記憶化搜索)

題目鏈接

題目大意：有N個人組成一支隊伍來答題，每個人答每道題的正確率都是已知的，但是有個要求：一直每個人答任何一道題目的時間都是1個小時，要求在任何時刻，任何兩個人的答題累計時間都不能超過1.求這樣答題的最優策略下最好的出題期望。

解題思路：把所有的人答題的累計時間作為狀態，用二進制數來表示。當這個二進制狀態每個位都是1的話，那麼就將這個二進制數清為0.復雜度2^10 * 1000；

代碼：

#include 
#include 
#include 
#include 

using namespace std;
const int maxn = 1500;
const double esp = 1e-9;

double f[maxn][maxn];
double P[maxn][maxn];

int n, m;

void init () {

    for (int i = 0; i <= m; i++)
        for (int j = 0; j <= (1< esp)
        return ans;

    if (k == m)
        return ans = 0;

    double tmp;
    for (int i = 0; i < n; i++) {

        if (st & (1<= 0)
            ans = max(ans, tmp + P[i][k]);
    }

    if (ans < 0)
        ans = -2;
    return ans;    
}

int main () {

    int T;
    scanf ("%d", &T);

    for (int cas = 1; cas <= T; 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]);

        init();

        printf ("Case #%d: %.5lf\n", cas, dp(0, 0));
    }
    return 0;    
}