CDOJ 1135 邱老师看电影 概率dp

点击打开链接

概率dp

代码：

#include <iostream>#include <cstring>#include <cstdio>using namespace std;const int maxn = 1e3+10;double dp[maxn][maxn];double dfs(int w,int b){	if(dp[w][b] >= 0) return dp[w][b];	if(w == 0) return 0;	if(b==0 && w!=0) return 1;	dp[w][b] = w*1.0/(w+b);	if(b >= 2){		double tb = b*1.0/(w+b) * (b-1)*1.0/(w+b-1); //要想在下一次取胜则本次学妹应该拿走一个黑鼠 邱也必须拿走一个黑鼠 酱神可以任意拿走一个白鼠或一个黑鼠		if(b >= 3)			dp[w][b] += tb * dfs(w,b-3) * (b-2)*1.0/(w+b-2);//酱神拿走黒鼠  学妹和邱老师各拿走一只黑鼠		if(w >= 1)			dp[w][b] += tb * dfs(w-1,b-2) * w*1.0/(w+b-2); //酱神拿走白鼠  	}	return dp[w][b];}int main(){	memset(dp,-1,sizeof(dp));	int w,b; cin >> w >> b;	PRintf("%.9f/n",dfs(w,b));}