付出 double 策略 limit 最优 printf 一行 math
桌面上有 R 张红牌和 B 张黑牌,随机打乱顺序后放在桌面上,开始一张一张地翻牌,翻到红牌得到 1 美元,黑牌则付出 1 美元。可以随时停止翻牌,在最优策略下平均能得到多少钱。
一行输入两个数 R,B, 其值在 0 到 5000 之间
在最优策略下平均能得到多少钱。
输出答案时, 小数点后第六位后的全部去掉, 不要四舍五入.
【分析】
概率 DP 这种东西想清楚就没问题。
f[i][j] 表示已经翻了 i 红 j 黑,之后最优策略下的期望得分。
因为直接 n^2 数组 0msT 了,所以滚动了一下。
View Code
- 1#include
- 2#include
- 3#include
- 4#include
- 5#include 6#include
- 7 using namespace std;
- 8 #defineMaxn 5010 9
- 10 doublef[2][Maxn];
- 11
- 12 doublemymax(doublex,doubley) {returnx>yx:y;}
- 13
- 14 int main()
- 15 {
- 16 int n,m;
- 17scanf("%d%d",&n,&m);
- 18f[n&1][m]=0;
- 19 for(inti=n;i>=0;i--)
- 20 {
- 21 intp=i&1,pp=p^1;
- 22 for(intj=m;j>=0;j--)
- 23 {
- 24 if(n==i) f[p][j]=mymax(f[p][j+1]-1,0);
- 25 else if(m==j) f[p][j]=mymax(f[pp][j]+1,0);
- 26 elsef[p][j]=mymax((f[pp][j]+1)*(n-i)/(n+m-i-j)+(f[p][j+1]-1)*(m-j)/(n+m-i-j),0);
- 27 }
- 28 }
- 29printf("%.6lf",f[0][0]-0.0000005);
- 30 return 0;
- 31}
2017-04-21 16:08:56
【BZOJ 1419】1419: Red is good (概率 DP)
来源: http://www.bubuko.com/infodetail-2033915.html