我是靠谱客的博主 彩色美女,最近开发中收集的这篇文章主要介绍Dinner Bet Gym - 101174D (期望dp)Problem D: Dinner Bet,觉得挺不错的,现在分享给大家,希望可以做个参考。
概述
Problem D: Dinner Bet
[ Time Limit: 1.5 s quad Memory Limit: 256 MiB ]
题意
题意是两个人在玩游戏,一共有(n)张牌,这两个人手上各有(m)张牌,然后对于每一轮操作,从总的(n)张牌中随机抽出(D)张牌,然后两个人手上含有这(D)张牌点数的牌被标记起来,在把(D)张牌放回(n)堆中,当有一个人手上的牌全部被标记过,游戏就结束,让你求这个游戏可以玩几轮的期望。
思路
一开始看到这个题我是束手无策的...不知道这些牌的点数怎么处理。?
考虑每张牌取到的概率是一样的,所以点数就变的不是那么重要了,我们可以考虑牌的点数把他们进行如下分类:
- 第一部分是仅第一个人有第二个人没有的牌。
- 第二部分是两个人都有的牌。
- 第三部分是仅第二个人有第一个人没有的牌。
设第二部分的牌有(B)张,那么很明显第一部分和第三部分都是(m-B)张,我们用(A)来表示,那么两个人手中一共出现的牌就是(tol = 2*A+B)张。
定义(dp[x][y][z])表示第一部分取了(x)个,第二部分取了(y)个,第三部分取了(z)个时,还可以玩几轮的期望。
首先,当(x+y==m || y+z==m)时,已经结束游戏,(dp[x][y][z] = 0)。
- 对于一次操作,可以看成第一部分新标记了(a)个,第二部分新标记了(b)个,第三部分新标记了(c)个,剩下的(D-a-b-c)不产生新的标记,设这个概率为(p[a][b][c]),那么就可以得出转移方程:
[ dp[x][y][z] = 1+sum_{a=0}^{A-x}sum_{b=0}^{B-y}sum_{c=0}^{A-z}p[a][b][c]*dp[x+a][y+b][z+c] ]
但是如此操作可能出现(a=b=c=0)的情况,需要单独拿出来,也就是:
[ dp[x][y][z] = 1+p[0][0][0]*dp[x][y][z]+sum_{a=0}^{A-x}sum_{b=0}^{B-y}sum_{c=0}^{A-z}p[a][b][c]*dp[x+a][y+b][z+c] \ ]
综合以上两个式子,可以得到
[ dp[x][y][z] = frac{1+sum_{a=0}^{A-x}sum_{b=0}^{B-y}sum_{c=0}^{A-z}p[a][b][c]*dp[x+a][y+b][z+c]}{1-p[0][0][0]} ]
其中分子部分不包括(a=b=c=0)情况。
接下来的只要求出(p[a][b][c])就可以得出(dp)了,考虑(dp[x][y][z]->dp[x+a][y+b][z+c])过程,可以得到
[ p[a][b][c] = frac{C_{A-x}^{a}*C_{B-y}^{b}*C_{A-z}^{c}*C_{x+y+z+n-tol}^{D-a-b-c}}{C_{n}^{D}} ]
然后用(dfs)就可以转移了。
#include <map>
#include <set>
#include <list>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#include <cfloat>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define
lowbit(x)
x & (-x)
#define
mes(a, b)
memset(a, b, sizeof a)
#define
fi
first
#define
se
second
#define
pii
pair<int, int>
#define
INOPEN
freopen("in.txt", "r", stdin)
#define
OUTOPEN
freopen("out.txt", "w", stdout)
typedef unsigned long long int ull;
typedef long long int ll;
const int
maxn = 1e5 + 10;
const int
maxm = 1e5 + 10;
const ll
mod
= 1e9 + 7;
const ll
INF
= 1e18 + 100;
const int
inf
= 0x3f3f3f3f;
const double pi
= acos(-1.0);
const double eps
= 1e-8;
using namespace std;
int n, m, A, B, D;
int cas, tol, T;
bool vis[100];
ll C[55][55];
double dp[12][12][12];
void handle() {
C[0][0] = 1;
C[1][0] = C[1][1] =1;
for(int i=2; i<=50; i++) {
for(int j=0; j<=i; j++) {
C[i][j] = j==0 ? 1 : C[i-1][j-1] + C[i-1][j];
}
}
}
void dfs(int x, int y, int z) {
if(x+y==m || y+z==m) {
dp[x][y][z] = 0;
return ;
}
if(dp[x][y][z] != -1.0) return ;
double t = 0, sum = 0;
for(int a=0; a<=A-x; a++) {
for(int b=0; b<=B-y; b++) {
for(int c=0; c<=A-z; c++) {
if(a+b+c > D)
continue;
if(a==0 && b==0 && c==0) {
t = 1.0*C[x+y+z+n-tol][D-a-b-c]/C[n][D];
continue;
} else {
dfs(x+a, y+b, z+c);
sum += 1.0*C[A-x][a]*C[B-y][b]*C[A-z][c]*C[x+y+z+n-tol][D-a-b-c]*dp[x+a][y+b][z+c]/C[n][D];
}
}
}
}
dp[x][y][z] = (1.0+sum)/(1.0-t);
return ;
}
int main() {
scanf("%d%d%d", &n, &D, &m);
handle();
mes(vis, 0);
for(int i=1, x; i<=m; i++) {
scanf("%d", &x);
vis[x] = true;
}
A = B = 0;
for(int i=1, x; i<=m; i++) {
scanf("%d", &x);
if(vis[x])
B++;
else
A++;
}
tol = 2*A+B;
for(int i=0; i<=A; i++) {
for(int j=0; j<=B; j++) {
for(int k=0; k<=A; k++) {
dp[i][j][k] = -1.0;
}
}
}
dfs(0, 0, 0);
printf("%.5fn", dp[0][0][0]);
return 0;
}
转载于:https://www.cnblogs.com/Jiaaaaaaaqi/p/10836260.html
最后
以上就是彩色美女为你收集整理的Dinner Bet Gym - 101174D (期望dp)Problem D: Dinner Bet的全部内容,希望文章能够帮你解决Dinner Bet Gym - 101174D (期望dp)Problem D: Dinner Bet所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复