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)堆中，当有一个人手上的牌全部被标记过，游戏就结束，让你求这个游戏可以玩几轮的期望。

思路

一开始看到这个题我是束手无策的...不知道这些牌的点数怎么处理。?
考虑每张牌取到的概率是一样的，所以点数就变的不是那么重要了，我们可以考虑牌的点数把他们进行如下分类：

1. 第一部分是仅第一个人有第二个人没有的牌。
2. 第二部分是两个人都有的牌。
3. 第三部分是仅第二个人有第一个人没有的牌。

设第二部分的牌有(B)张，那么很明显第一部分和第三部分都是(m-B)张，我们用(A)来表示，那么两个人手中一共出现的牌就是(tol = 2*A+B)张。
定义(dp[x][y][z])表示第一部分取了(x)个，第二部分取了(y)个，第三部分取了(z)个时，还可以玩几轮的期望。

1. 首先，当(x+y==m || y+z==m)时，已经结束游戏，(dp[x][y][z] = 0)。

2. 对于一次操作，可以看成第一部分新标记了(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;
}