Alice和Bob赌糖果(概率dp)
链接https://ac.nowcoder.com/acm/problem/14962
来源：牛客网
题目描述Alice和Bob赌糖果。规则是这样的：Alice从[ l, r]中随机抽一个数，Bob从[ L, R]中随机抽一个数，谁抽的数大谁就赢，输的一方给另一方1颗糖（平局不用给糖），他们会一直赌下去直到有一方没有糖果为止。Alice有n颗糖果，Bob有m颗糖果，求Alice将Bob的糖果赢完的概率。
输入描述第一行3个整数n, l, r。
第二行3个整数m, L, R。
Alice将Bob糖果赢完的概率，结果保留5位小数。
示例1输入
1 1 3
1 1 2
输出
0.75000
输入
0 1 100
1 1 100
输出
0.00000
0 <= n,m 0
1 <= l <= r <= 100,1 <= L <= R <= 100
首先我们大致理解下题意：Alice起始位置在坐标轴的n点，他往右走一格的概率是ppp，往左走一格的概率是1−p1-p1−p,题目要求的则是Alice走到n+mn+mn+m处的概率。
思路：假设Alice赢的概率为ppp,输的概率则为1−p1-p1−p，当Alice有iii颗糖果时，其将Bob的糖果赢完的概率设为fif_ifi,可列出以下方程：
f0=0, fn+m=1f_0 = 0,\ f_{n+m} = 1f0=0, fn+m=1
fi=(1−p)fi−1+pfi+1 (1)f_i=(1-p)f_{i-1}+pf_{i+1}\ (1)fi=(1−p)fi−1+pfi+1 (1)
根据题目fn+m=1f_{n+m}=1fn+m=1 我们采用倒推，假设fi=kifi+1f_i=k_if_{i+1}fi=kifi+1带入（1）式中得到kik_iki的递推关系式：
ki=p1−(1−p)ki−1(2)k_i=\frac{p}{1-(1-p)k_{i-1}}(2)ki=1−(1−p)ki−1p(2)
∵\because∵f0=0f1f_0=0f_1f0=0f1∴\therefore∴ k0=0k_0=0k0=0
综上述可知答案为fn=∏i=nn+m−1kif_n=\prod_{i=n}^{n+m-1}k_ifn=∏i=nn+m−1ki
#include
using namespace std;
double calc(int a, int b, double p){
double ans = 1.0, k = 0.0;
for(int i = 1; i = a) ans *= k;
}
return ans;
}
int main(){
int n, l, r, m, L, R;
scanf("%d%d%d%d%d%d", &n, &l, &r, &m, &L, &R);
if(!n) printf("0.00000");//特判Alice开始没有糖果的时候，赢的概率为0
else{
int t1 = 0, t2 = 0;
for(int i = l; i <= r; i++)
for(int j = L; j j) t1++;//Alice赢的次数
else if(i < j) t2++;//Bob赢的次数,平局对结果无影响不考虑
}
double p = t1 * 1.0 / double(t1 + t2);//注意精度
double ans = calc(n, n+m, p);//Alice从开始的n个糖果数到赢得所有n+m的糖果数的概率
printf("%.5f\n",ans);
}
return 0;
}
Sin陌
原创文章 1获赞 3访问量 55
关注
私信
展开阅读全文
作者：Sin陌
