首页 > 代码库 > SRM 626 D1L1: FixedDiceGameDiv1,贝叶斯公式,dp
SRM 626 D1L1: FixedDiceGameDiv1,贝叶斯公式,dp
题目:http://community.topcoder.com/stat?c=problem_statement&pm=13239&rd=15859
用到了概率论中的贝叶斯公式,而贝叶斯公式中须要用到的概率须要用dp方法求解。
代码:
#include <algorithm> #include <functional> #include <numeric> #include <utility> #include <iostream> #include <sstream> #include <iomanip> #include <bitset> #include <string> #include <vector> #include <stack> #include <deque> #include <queue> #include <set> #include <map> #include <cstdio> #include <cstdlib> #include <cctype> #include <cmath> #include <cstring> #include <ctime> #include <climits> using namespace std; #define CHECKTIME() printf("%.2lf\n", (double)clock() / CLOCKS_PER_SEC) typedef pair<int, int> pii; typedef long long llong; typedef pair<llong, llong> 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 ************************/
SRM 626 D1L1: FixedDiceGameDiv1,贝叶斯公式,dp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。