Contest

   
   

    
    1
2 3
0.6 0.3 0.4
0.3 0.7 0.9
   
   

   
   

    
    Case #1: 2.20000
   
   

解题思路：

题意为有n个学生，m道题，已知每位学生对每一个题都有一个答对的可能性，要求一道题目仅仅能一个学生做。一个学生能够做多道。 且随意两个学生之间做的题目之差不能超过1，问m道题所有答对的最大可能性为多少。

n最大为10。所以最多有 0~(2的10次方-1）种状态，每一位代表一个学生。1表示答题。0表示不答题。

当dp[ i ] [ j ]代表前 i  道题，状态为 j 的所有答对最大可能性。状态为j，也就是二进制里面包含i个1，由于要选i个人答题。

比方 dp[ 2 ][ 4]，  4 可能是1001 1100 0011  0101等。仅仅要包含2个1就能够。 n<=m的时候

状态转移方程为：  dp [  i +1 ]  [ j ]= max(dp[i+1][j], dp[i-1][ s] + p[ k ][ i ] ） s是一个状态，p[k][i]表示第k个人答对第i道题的可能性

从已知状态推未知状态。

n>m时。由于随意两个学生做的题目仅仅差不能超过1，所以 当全部学生都答过一道题以后，状态要从0開始， dp[i][ (1<<n)-1]已知。也就是dp[i][0]已知

參考：http://www.2cto.com/kf/201409/338936.html

代码：

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
const int Max=(1<<10)+1;
double dp[1001][Max];//代表前i道题，状态为j做出来题目的最大期望
double p[11][1001];
int n,m;
int s;//最大状态

double  solve()
{
    double ans=-1.0;
    dp[0][0]=0;
    for(int i=0;i<m;i++)//第几道题
        for(int j=0;j<s;j++)
        {
            if(dp[i][j]<0)//眼下该状态还没出现
                continue;
            for(int k=0;k<n;k++)//第几个人来做
            {
                if(!((1<<k)&j))//第k个人可选,也就是j的二进制第k位为0
                {
                    int temps=j|(1<<k);
                    if(temps==(s-1))
                        temps=0;
                    dp[i+1][temps]=max(dp[i+1][temps],dp[i][j]+p[k][i]);
                }
            }
        }
    for(int i=0;i<s;i++)
        if(ans<dp[m][i])
        ans=dp[m][i];
    return ans;
}
int main()
{
    int t;scanf("%d",&t);
    for(int ca=1;ca<=t;ca++)
    {
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
            scanf("%lf",&p[i][j]);
        s=1<<n;
        for(int i=0;i<=m;i++)
            for(int j=0;j<s;j++)
            dp[i][j]=-1.0;
        double ans=solve();
        printf("Case #%d: %.5lf\n",ca,ans);
    }
    return 0;
}