首页 > 代码库 > POJ 2906 数学期望
POJ 2906 数学期望
开始时直接设了一个状态,dp[i][j]为发现i种bug，j个系统有bug的期望天数。但很错误，没能转移下去。。。。
看了题解，设状态dp[i][j]为已发现i种bug，j个系统有bug，到完成目标状态所需要的期望的天数。妙啊，这样一设状态，就很好更解了。如，由dp[i][j]
可以到达状态dp[i][j+1]，则到达它的概率很明显可求出为p=(i/n)*((s-j)/s)，则是，需要dp[i][j+1]（期望）天数的概率就是p。这就很容易理解了啊，高！高！高！
由dp[i][j]可以转移出四个状态，分别是a1=dp[i][j],a2=dp[i+1][j+1],a3=dp[i][j+1],a4=dp[i+1][j]。分别对应概率p1,p2...
则有方程dp[i][j]=sum(ai*pi)+1.最后要加1是因为，必须要花费一天。
于是，
#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int N=1010;double dp[N][N];int main(){ int n,s; while(~scanf("%d%d",&n,&s)){ dp[n][s]=0; for(int i=n;i>=0;i--) for(int j=s;j>=0;j--){ if(i==n && j==s) continue; dp[i][j]=(i*(s-j)*dp[i][j+1]+(n-i)*j*dp[i+1][j]+(n-i)*(s-j)*dp[i+1][j+1]+n*s)/(n*s-i*j); } printf("%.4f\n",dp[0][0]); } return 0;}
POJ 2906 数学期望
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。