首页 > 代码库 > 【BZOJ】1419 Red is good
【BZOJ】1419 Red is good
【算法】期望DP
【题解】其实把状态表示出来就是很简单的期望DP。
f[i][j]表示i张红牌,j张黑牌的期望。
i=0时,f[0][j]=0。
j=0时,f[i][0]=i。
f[i][j]=max(0,i/(i+j)*(f[i-1][j]+1)+j/(i+j)*(f[i][j-1]-1))。
直接使用期望定义式E(X)=Σpi*xi
不四舍五入就是在后一位-5。
空间限制必须用递推+滚动数组。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=5100; double f[2][maxn]; int r,b,x=0; int main() { scanf("%d%d",&r,&b); for(int i=1;i<=r;i++) { f[x][0]=i; for(int j=1;j<=b;j++) f[x][j]=max(0.0,1.0*i/(i+j)*(1+f[1-x][j])+1.0*j/(i+j)*(-1+f[x][j-1])); x=1-x; } printf("%.6lf\n",f[1-x][b]-5e-7); return 0; }
【BZOJ】1419 Red is good
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。