BZOJ 1419 Red is goooooood

发表于 | 更新于

Link

Solution

一开始naive的认为，可以用一遍递推，求出翻到第i张牌，R或者B的期望剩余张数，就可以算出概率了。。 但是怎么想怎么玄，一写果然WA了。 后来想想，期望除了线性性之外好像没有什么好用的性质。我这样用期望算概率，里面有期望除期望，难免有种钦定的感觉。 没什么办法，去看题解。

考虑用f[i][j]表示剩下i张红牌，j张黑牌时的最大期望。 当i=0时，f[i][j]=0; 当j=0时，f[i][j]=i; 其他情况，f[i][j]=max(0,i/(i+j) (f[i-1][j]+1)+j/(i+j) (f[i][j-1]-1)). 于是滚动一下qwq。 ——fqk

好像。。不是很难的样子。。学习了。 发现期望DP有一个特点就是，设计出状态的转移必须符合期望的定义形式（或许是我做题太少？），而概率DP就不一样。 upd:如果期望累加的话也可以不用，但这样的最优期望是必须的。

AND，像期望出现在分母里的这种事就算了吧

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//Code by Lucida
#include<bits/stdc++.h>
#define red(x) scanf("%d",&x)
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=5000+1;
typedef long double ld;
const ld INF=1e100;
using std::max;
ld P(ld a,ld b){return a/b;}
int main()
{
	//freopen("input","r",stdin);
	static ld f[2][MAXN];
	int R,B;red(R),red(B);
	//f[r][b] 用完r b张牌的时候的期望
	//不行。前面的依赖后面的
	//./
	// \
	// 这样分叉，必须从后往前走，从前往后算不了
	// f[r][b] 还剩r b张牌时候的期望
	for(int r=0;r<=R;r++)
		for(int b=0;b<=B;b++)
		{
			if(!r) f[r&1][b]=0;
			else if(!b) f[r&1][b]=r;
			else f[r&1][b]=max((ld)0,P(r,r+b)*(1+f[r&1^1][b])+P(b,r+b)*(-1+f[r&1][b-1]));
		}
	printf("%.6lf\n",(double)(f[R&1][B]-5e-7));
	return 0;
}