小C打比赛

NC14942. 小C打比赛

描述

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

输入描述

第一行两个正整数n,m
接下来一共n行，每行有m个小数，第i行的第j个小数表示p_i,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

上次编辑到这里，代码来自缓存点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 8ms, 内存消耗: 512K, 提交时间: 2018-01-20 13:49:06

#include<cstdio>
#include<algorithm>
using namespace std;
double ans,dp[1<<8][200],a[8][200];
int n,m;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;++i) for(int j=1;j<=m;++j) scanf("%lf",&a[i][j]);
	for(int i=1;i<(1<<n);++i) for(int j=1;j<=m;++j) {for(int x=0;x<n;++x)
 	if((1<<x)&i) {
 	double t=0;
	for(int y=1;y<=j;++y) t+=(dp[i^(1<<x)][j-y]+1)*a[x][y];
	dp[i][j]=max(dp[i][j],t);
 	ans=max(ans,dp[i][j]);
	}
	}
 	printf("%.5f\n",ans);
}