BZOJ1491 Red is good

题目链接：Click here

Solution:

考虑设\(f(i,j)\)表示当前还有\(i\)张红牌，\(j\)张黑牌时的期望收益

易得状态转移方程：\(f(i,j)=\frac{i}{i+j}(f(i-1,j)+1)+\frac{j}{i+j}(f(i,j-1)-1)\)

事实上，由于采取最优策略，当此时期望为负数时，我们肯定是不取的，所以式子是这样的:

\[f(i,j)=max(0,\frac{i}{i+j}(f(i-1,j)+1)+\frac{j}{i+j}(f(i,j-1)-1))
\]

题目只给了64MB的空间，所以我们需要用滚动数组来优化空间

最后再对输出进行一些处理就可以了

Code:

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int v=1e6;

int n,m,u=1;

double f[2][5001];

int read(){

	int x=0,f=1;char ch=getchar();

	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

	while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}

	return x*f;

}

int main(){

	n=read(),m=read();

	for(int i=0;i<=n;i++){

		u^=1;f[u][0]=i;

		for(int j=1;j<=m;j++)

			f[u][j]=max(0.0,1.0*i/(i+j)*(f[u^1][j]+1)+1.0*j/(i+j)*(f[u][j-1]-1));

	}

	printf("%.6lf",1.0*(ll){f[u][m]*v}/v);

	return 0;

}

巴特西

BZOJ1491 Red is good

Solution:

Code:

最新文章

热门文章