HDU4870 Rating(概率)

第一场多校，感觉自己都跳去看坑自己的题目里去了，很多自己可能会比较擅长一点的题目没看，然后写一下其中一道概率题的题解吧，感觉和自己前几天做的概率dp的思路是一样的。下面先来看题意：一个人有两个TC的账号，一开始两个账号rating都是0,然后每次它会选择里面rating较小的一个账号去打比赛，每次比赛有p的概率+1分，有1-p的概率－2分，当然如果本身是<=2分的也就还是回到0分。然后问最后其中一个账号到达20分时需要打多少次比赛。

先考虑一场比赛的情况，定义dp[k]为当前为k分，要达到20分时的期望回合数。(令q=1-p)

那么显然有 dp[0]=1+p*dp[1]+q*dp[0] 化简得 dp[0]=1/p+dp[1]

dp[1]=1+p*dp[2]+q*dp[0] 化简得 dp[0]=1/p+1/p^2+dp[2]

我们令 dp[0]=tk+dp[k] 那么tk就表示由0状态到达k状态所需的期望回合数。那么显然如果是要到达20分的话，答案就是t20

然后我们看 dp[k]=1+p*dp[k+1]+q*dp[k-2] 代入dp[0]=dp[k]+tk 就有

dp[0]=1/p+1/p*t[k]-(1-p)/p*t[k-2]+dp[k+1]

所以 t[k+1]＝1/p+1/p*t[k]-(1-p)/p*t[k-2]

边界条件是 t[0]=0,t[1]=1/p,t[2]=1/p+1/p^2

知道这些就可以递推出所有需要的t[k]了。

现在我们来看如果有两个账号怎么破。首先我们必然是（0,0）->(0,1)->(1,1)->(1,2)->(2,2)－>(2,3)->(3,3)...

(0,0)->(0,1)需要的期望回合数是t[1]-t[0]. (0,1)->(1,1)需要的期望回合数是 t[1]-t[0]

(1,1)->(1,2)需要的期望回合数是t[2]-t[1]. (1,2)->(2,2)需要的期望回合数是 t[2]-t[1].

....

(18,18)->(18,19)需要的期望回合数是t[19]-t[18]. (18,19)->(19,19)需要的期望回合数是t[19]-t[18].

(19,19)->(19,20)需要的期望回合数是t[20]-t[19]。

全部加起来的结果就是t[19]*2+t[20]-t[19].

所以最后的复杂度可以是线性的，而且理论上对于k个账号也是适用的，这样就可以避开了高斯消元的做法了。

#pragma warning(disable:4996)

#include<iostream>

#include<cstring>

#include<string>

#include<algorithm>

#include<cstdio>

#include<vector>

#include<cmath>

#include<queue>

#define ll long long

#define maxn 10000

#define maxe 30000

#define inf 0x3f3f3f3f

using namespace std;

double p;

double t[25];

int main()

{

	while (cin >> p){

		t[0] = 0;

		t[1] = 1 / p;

		t[2] = 1 / p + 1 / (p*p);

		for (int i = 3; i <= 20; i++){

			t[i] = 1 / p + 1 / p*t[i - 1] - (1 - p) / p*t[i - 3];

		}

		double ans = t[19] * 2 + t[20] - t[19];

		printf("%.6lf\n", ans);

	}

	return 0;

}

巴特西

HDU4870 Rating(概率)

最新文章

热门文章