问题 J: Red is good
时间限制: 1 Sec 内存限制: 64 MB 提交: 15 解决: 7 题目描述 桌面上有R张红牌和B张黑牌,随机打乱顺序后放在桌面上,开始一张一张地翻牌,翻到红牌得到1美元,黑牌则付出1美元。可以随时停止翻牌,在最优策略下平均能得到多少钱。 输入 一行输入两个数R,B,其值在0到5000之间 输出 在最优策略下平均能得到多少钱。 样例输入 5 1 样例输出 4.166666 提示 输出答案时,小数点后第六位后的全部去掉,不要四舍五入.状态转移挺有意思的,f[i][j]表示牌堆初始有i张红牌,j张黑牌,那么转移:如果第一次抽到红牌,那么概率为i/(i+j),抽完这张红牌后还剩下i-1张红牌,j张黑牌,那不就是f[i-1][j]了么。第一次抽到黑牌以此类推。
f[i][0]=i; f[i][j]=max(0,(f[i-1][j]+1)*i/(i+j)+(f[i][j-1]-1)*j/(i+j)); 不四舍五入还是挺简单的,用int卡一下即可。#include#include #include #include #include using namespace std;double f[3][5005];int n,m;int main(){ cin>>n>>m; for(int i=0;i<=n;i++) { int k=i%2;f[k][0]=i; for(int j=1;j<=m;j++) f[k][j]=max(0.0,(f[k][j-1]-1.0)*(double)j/(i+j)+(f[k^1][j]+1.0)*(double)i/(i+j)); } int ans=f[n%2][m]*1000000; printf("%.6lf",(double)ans/1000000);}