本文主要是介绍poj 2096 概率dp,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
http://poj.org/problem?id=2096
G++ WA C++ AC
题解看这个吧:我没看懂题目,所以找的题解翻译:http://blog.csdn.net/morgan_xww/article/details/6774708
但是题解里感觉有一点写的不好---初始化应该有两部分:1、dp[s][n]=0.0,以及dp[s+1][j]=0.0 上面那个博客里没有初始化dp[s+1][j]=0.0 因为全局变量
我的dp[i][j]意思是,前i个子系统,前j种bug的天数期望。
其实这道概率DP入门题让我学到的是一种高中学概率没用的的思维方式----由后一阶段推前一阶段的概率/期望
#include <cstdio>
#include <iostream>
using namespace std;#define rep(i,s,e) for(int i=s;i<e;i++)
#define reped(i,s,e) for(int i=s;i>=e;i--)
const int MAXN = 1000+100;int n,s;double dp[MAXN][MAXN];double solve()
{dp[s][n]=0.0;rep(i,0,n+1)dp[s+1][i]=0.0;reped(i,s,0){reped(j,n,0){if(i==s && j==n)continue;dp[i][j]=(n*s+(s-i)*j*dp[i+1][j]+(s-i)*(n-j)*dp[i+1][j+1]+i*(n-j)*dp[i][j+1])/(n*s-i*j);}}return dp[0][0];
}int main()
{while(~scanf("%d%d",&n,&s)){printf("%.4lf\n",solve());}return 0;
}
这篇关于poj 2096 概率dp的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!