题目链接

题意：有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; }