首页 > 代码库 > sgu495：概率dp / 推公式
sgu495：概率dp / 推公式
概率题。。可以dp也可以推公式
抽象出来的题目大意：
有 n个小球，有放回的取m次 问 被取出来过的小球的个数的期望
dp维护两个状态 第 i 次取出的是 没有被取出来过的小球的 概率dp[i] 和取出的是已经被取出来过的小球的概率np[i];
如果第 i-1 次取出的是已经被取出来过的小球 那么第 i 次取出没有取出来过小球的概率即为 dp[i-1]；
反之则为 dp[i-1] - 1/n（没有取出来过的小球少了一个）
所以可以得到状态转移方程 dp[i]=dp[i-1]*(dp[i-1]-1/n)+np[i-1]*dp[i-1];
还可以推公式。。不过我还是觉得 推公式 得靠人品，能yy出来那当然是极好的。。。
代码：
#include <iostream>#include <stdio.h>#include<string.h>#include<algorithm>#include<string>#include<math.h>#include<ctype.h>using namespace std;#define MAXN 10000int n,m;double dp[100010];double np[100010];double solve(){ double res=0; memset(dp,0,sizeof(dp)); memset(np,0,sizeof(np)); dp[1]=1; np[1]=0; for(int i=2;i<=m;i++) { dp[i]=dp[i-1]*(dp[i-1]-1.0/(double)n)+np[i-1]*dp[i-1]; np[i]=1-dp[i]; } for(int i=1;i<=m;i++) { res+=dp[i]; } return res;}int main(){ while(scanf("%d%d",&n,&m)!=EOF) { printf("%.10lf\n",solve()); } return 0;}
公式。。
#include <stdio.h>#include<math.h>double n,m;int main(){ while(scanf("%lf%lf",&n,&m)!=EOF) { printf("%.10lf\n",n-n*pow(((n-1)/n),m)); } return 0;}
sgu495：概率dp / 推公式
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。