返回信息流如图所示，现在能想到方法比2^n稍稍简单一点，有哪位大神知道能用的算法呢？
这是一条镜像帖。来源：北邮人论坛 / cpp / #95039同步于 2017/4/7
该镜像源已超过 30 天没有更新，可能在源站已被删除。
CPP机器人发帖
【问题】京东的这道题有时间复杂度低的算法吗？
zhangzan
2017/4/7镜像同步11 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
#include<bits/stdc++.h>
using namespace std;
float cache[101][101];
float pro[101];
int n,k;
float dfs(int d,int c)
{
if(d==n) return c>=k?1.0:0.0;
float& ret=cache[d][c];
if(ret!=-1.0) return ret;
ret = (1-pro[c])*dfs(d+1,c) + pro[c]*dfs(d+1,c+1);
return ret;
}
int main()
{
for(int i=0;i<101;++i)for(int j=0;j<101;++j)cache[i][j]=-1.0;
cin>>n;
for(int i=0;i<n;++i)
{
int curr;cin>>curr;
pro[i]=float(curr)/100;
}
k=n*3/5;
if(k/3*5!=n)k++;
cout<<fixed<<setprecision(5)<<dfs(0,0)<<endl;
return 0;
}
这是我的答案，但是不知道为啥错了。。。[ema1]
【 在 pzhfreeze 的大作中提到: 】
: DP时间复杂度O(n^2)，空间复杂度O(n)，用Python简单地写了一下。
[upload=1][/upload]
你这个代码稍微有点问题，考虑dp[1]每次都是p(i - 1) + 后边，比如i = 1, dp[1] = p0;i = 2时，dp[1] = p1 + (1 - p1) * p0，此处不对，应为：dp[1] = p1 * (1 - p0) + (1- p1) * p0;
dp[i] 表示的是通过考试门数为i的概率没错吧？
你这是最简单的情况。。代码里是含有你这种情况的。。
状态方程为dp[j]=p[i-1]*dp[j-1]+(1-p[i-1])*dp[j]，当j=1时就是你这种情况哈。。
【 在 dxy1 的大作中提到: 】
: [upload=1][/upload]
: 你这个代码稍微有点问题，考虑dp[1]每次都是p(i - 1) + 后边，比如i = 1, dp[1] = p0;i = 2时，dp[1] = p1 + (1 - p1) * p0，此处不对，应为：dp[1] = p1 * (1 - p0) + (1- p1) * p0;
: dp[i] 表示的是通过考试门数为i的概率没错吧？