题目描述    https://www.nowcoder.com/acm/contest/57/C

小C现在要参加一场wannafly挑战赛，一场挑战赛一共有n道题，一共有m分钟。
对于第i道题，小C解决它需要恰好j分钟的概率是p i,j。
小C每次会选择某一道没做完的题，然后把它解决（不能中途放弃），之后再决策下一道要做的题是哪道。
求小C在最优策略下，期望能做出几道题。

输入描述:

第一行两个正整数n,m
接下来一共n行，每行有m个小数，第i行的第j个小数表示pi,j（这里假设不存在0分钟A题的dalao）。

输出描述:

输出一个小数，表示期望能做出几道题，保留小数点后五位。
示例1

输入

2 5
0.2 0.2 0.2 0.2 0.2
0 0.25 0.25 0.25 0.25

输出

1.30000

备注:

1≤ n≤ 6,1≤ m≤ 180
每道题的概率和为1(每道题只要时间够一定能做出来)
输入最多四位小数

一个状态压缩已经这么费劲了么…………

dp[时间][二进制表示的状态]=期望

循环也对

转移方程写错了  cur+=(1+dp[i-q][j])*t[k+1][q];

然后对于同一个状态取得是不同时间分配的最优方案

还是没有理解明白转移啊 

（前一种状态的期望+当前这个题对了加一题）*这个题作对的概率

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;
double t[200][200],dp[200][200];
int main()
{
   // freopen("cin.txt","r",stdin);
    while(~scanf("%d%d",&n,&m))
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                scanf("%lf",&t[i][j]);
        for(int i=0;i<200;i++)
            for(int j=0;j<200;j++)
                dp[i][j]=0.0;
        for(int i=1;i<=m;i++)
        {
            for(int j=0;j<(1<<n);j++)
            {
                for(int k=0;k<n;k++)
                {
                    if(!(j&(1<<k)))
                    {
                        double cur=0.0;
                        for(int q=1;q<=i;q++)
                            cur+=(1+dp[i-q][j])*t[k+1][q];
                        dp[i][j|(1<<k)]=max(dp[i][j|(1<<k)],cur);
                    }
                }
            }
        }
        printf("%.5lf\n",dp[m][(1<<n)-1]);

    }
    return 0;
}