本文主要是介绍lightoj 1050 - Marbles （概率DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
思路：定义dp[i][j] 为 袋子中有i个红球和j个红球时获胜的概率
那么根据题意我只可以任意拿而对手只拿蓝球。那么
dp[i][j] = （拿到红球的概率） * dp[i-1][j-1] + (拿到蓝球的概率) * dp[i][j-2];
边界：当红球没有时，获胜的概率为1
注意点：T比较大，需要把所有数据预处理出来直接查询，否则超时
/************************************************ Author: fisty* Created Time: 2015-08-23 10:40:51* File Name : 1050.cpp*********************************************** */
#include <iostream>
#include <cstring>
#include <deque>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <algorithm>
using namespace std;
#define Debug(x) cout << #x << " " << x <<endl
#define Memset(x, a) memset(x, a, sizeof(x))
const int INF = 0x3f3f3f3f;
typedef long long LL;
typedef pair<int, int> P;
#define FOR(i, a, b) for(int i = a;i < b; i++)
#define lson l, m, k<<1
#define rson m+1, r, k<<1|1
#define MAX_N 510
int t;
int Red, Blue;
double dp[MAX_N][MAX_N];
double init(){Memset(dp, 0);for(int i = 1;i <= MAX_N; i++){dp[0][i] = 1;}for(int i = 1;i < MAX_N; i++){for(int j = 2;j < MAX_N; j++){dp[i][j] = ((double)i / (double)(i + j) * dp[i-1][j-1]) + (j / (double)(i + j) * dp[i][j-2]); }}
}int main() {//freopen("in.cpp", "r", stdin);//cin.tie(0);//ios::sync_with_stdio(false);int cnt = 1;scanf("%d", &t);init();while(t--){scanf("%d%d", &Red, &Blue);printf("Case %d: ", cnt++);double ans = dp[Red][Blue];if( ans >= -1e-7 && ans <= 1e-7)printf("0\n");elseprintf("%lf\n", ans);}return 0;
}
这篇关于lightoj 1050 - Marbles （概率DP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
