hdu5045Contest 概率dp

//已知N个人对M道题做对的概率
//如何安排这N个人做这M道题使得其期望最大
//要求随意时间随意两个人的做题差不大于1。换句话说。就是在没N道题中必须是不同的人做
//能够用dp[i][j] 表示做到第i道题。且做题情况是j状态得到的最大期望
//因为每N道题必须是不同的N个人做，所以当j的状态达到(1<<n)-1是将状态转移到0
//dp[i][k] = max(dp[i][k] , p[j+1][i] + dp[i-1][k^(1<<j)])  ;
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std ;
const int maxn = 1010 ;
double dp[maxn][1<<10] ;
double p[100][maxn] ;
int main()
{
  //  freopen("in.txt","r" , stdin) ;
    int T , n , m ;
    int cas  = 0 ;
    scanf("%d" , &T) ;
    while(T--)
    {
        scanf("%d%d" , &n, &m) ;
        for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++)
        scanf("%lf" , &p[i][j]) ;
        for(int i = 0;i <= m;i++)
        for(int j = 0;j < (1<<n) ;j++)
        dp[i][j] = -1 ;
        dp[0][0] = 0 ;
        for(int i = 1;i <= m;i++)
        {
            for(int j = 0;j < n;j++)
            for(int k = 1;k <= ((1<<n)-1);k++)
            {
                if((k&(1<<j)) == 0)continue ;
                if(dp[i-1][k^(1<<j)] == -1)
                continue ;
                dp[i][k] = max(dp[i][k] , p[j+1][i] + dp[i-1][k^(1<<j)])  ;
            }
            if(i%n == 0)
            {
               dp[i][0] = dp[i][(1<<n)-1] ;
               dp[i][(1<<n)-1] = -1 ;
            }
        }
        double sum = 0;
        for(int i = 0;i < (1<<n)-1 ;i++)
        sum = max(sum , dp[m][i]);
        printf("Case #%d: ",++cas) ;
        printf("%.5lf " ,sum) ;
    }
    return 0 ;
}