首页 > 代码库 > 1419: Red is good
1419: Red is good
1419: Red is good
Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 773 Solved: 320
[Submit][Status][Discuss]
Description
桌面上有R张红牌和B张黑牌，随机打乱顺序后放在桌面上，开始一张一张地翻牌，翻到红牌得到1美元，黑牌则付出1美元。可以随时停止翻牌，在最优策略下平均能得到多少钱。
Input
一行输入两个数R,B,其值在0到5000之间
Output
在最优策略下平均能得到多少钱。
Sample Input
5 1
Sample Output
4.166666
HINT
输出答案时,小数点后第六位后的全部去掉,不要四舍五入.
Source
概率期望DP
f[i][j]表示有i张红j张黑情况下的期望收益
f[i][j]=max(0,i/(i+j)*(f[i-1][j]+1)+j/(i+j)*(f[i][j-1]-1))
转移是和很好理解的，如果选了的期望收益<0，那么不如不选
ps:
1、滚动数组压内存
2、去尾，不是四舍五入
#include<cstdio>#include<cstring>#include<iostream>using namespace std;const int N=5005;int n,m;double f[2][N];int main(){ scanf("%d%d",&n,&m); int now=0; for(int i=1;i<=n;i++){ now^=1; f[now][0]=i; for(int j=1;j<=m;j++){ f[now][j]=max(0.0,(f[now^1][j]+1)*i/(i+j)+(f[now][j-1]-1)*j/(i+j)); } } char ans[35]; sprintf(ans,"%.7lf",f[now][m]); int len=strlen(ans);ans[len-1]=0; puts(ans); return 0;}
1419: Red is good
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。