Wannafly挑战赛8 - C.小C打比赛

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

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述 

小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(每道题只要时间够一定能做出来)
输入最多四位小数

代码：

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<string>
#include<queue>
#include<vector>
#include<set>
#include<iomanip>
using namespace std;
int n,m;
double a[9][209],dp[109][209];
int main()
{
    scanf("%d%d",&n,&m);
    int i,j,k,l;
    double tmp;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            scanf("%lf",&a[i][j]);

    for(i=1;i<(1<<n);i++) //枚举不同选择方案
    for(j=1;j<=m;j++)     //枚举花费时间
    {
        for(k=1;k<=n;k++) //当前这种方案i都是用了哪道题
        if(i&(1<<(k-1)))  //用了题目k
        {
            for(l=1,tmp=0;l<=j;l++)     //用l分钟做k题目
                tmp+=(1+dp[i^(1<<(k-1))][j-l])*a[k][l]; //i^(1<<k-1)即未选k时的方案，这里dp[i][j]计算的是期望
            dp[i][j]=max(dp[i][j],tmp);
        }
    }
    printf("%.5f\n",dp[(1<<n)-1][m]);
    return 0;
}