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; }