程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> SRM 626 D1L1: FixedDiceGameDiv1，貝葉斯公式，dp

SRM 626 D1L1: FixedDiceGameDiv1，貝葉斯公式，dp

編輯：C++入門知識

用到了概率論中的貝葉斯公式，而貝葉斯公式中需要用到的概率需要用dp方法求解。

代碼：

#include 
#include 
#include 
#include 
#include 
#include 
#include 

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#define CHECKTIME() printf(%.2lf
, (double)clock() / CLOCKS_PER_SEC)
typedef pair pii;
typedef long long llong;
typedef pair pll;
#define mkp make_pair

/*************** Program Begin **********************/
const int MAX_SCORE = 50 * 50;
class FixedDiceGameDiv1 {
public:
	double dp1[MAX_SCORE + 1], dp2[MAX_SCORE + 1];

	// dp[i]: roll a b-sieded dice 最後總得分為i的概率
	void calc(int a, int b, double dp[])
	{
		for (int i = 0; i < MAX_SCORE + 1; i++) {
			dp[i] = 0.0;
		}
		dp[0] = 1.0;
		for (int i = 0; i < a; i++) {
			for (int j = a * b; j >= 0; j--) {
				if (dp[j] == 0) {
					continue;
				}
				for (int k = 1; k <= b; k++) {
					dp[j + k] += dp[j] / b;
				}
				dp[j] = 0;
			}
		}
	}
	double getExpectation(int a, int b, int c, int d) {
		double res = 0.0;

		calc(a, b, dp1);
		calc(c, d, dp2);

		// 貝葉斯公式
		double up = 0, down = 0;
		for (int i = a; i <= a * b; i++) {
			for (int j = 0; j < i; j++) {
				up += dp1[i] * dp2[j] * i;
				down += dp1[i] * dp2[j];
			}
		}

		if (down == 0) {
			return -1;
		}
		res = up / down;

		return res;
	}

};

/************** Program End ************************/