[BZOJ1419] Red is good(期望DP)
2024-09-08 06:12:37
逆推
只不过顺序还是顺着的,思想是逆着的
f[i][j]表示还剩下i张红牌,j张黑牌的期望值
那么边界是
f[i][0]=i,因为只剩i张红牌
f[0][j]=0,只剩黑牌,显然直接停止最优
f[i][j] = max(0,i/(i+j)*f[i-1][j]+j/(i+j)*f[i][j-1])
空间不够,开两层即可
#include <cstdio>
#include <iostream>
#define N 5001 int n, m;
double f[2][N];
//逆推,f[i][j]表示还剩下i张红牌,j张黑牌的期望 int main()
{
int i, j, now;
scanf("%d %d", &n, &m);
for(i = 0; i <= n; i++)
{
now = i & 1;
f[now][0] = i;
for(j = 1; j <= m; j++)
f[now][j] = std::max(0.0, 1.0 * i / (i + j) * (f[now ^ 1][j] + 1) + 1.0 * j / (i + j) * (f[now][j - 1] - 1));
}
printf("%.6lf\n", f[n & 1][m] - 0.0000005);
return 0;
}
最新文章
- WCF调用
- Shell: test
- linux笔记:shell基础-环境变量配置文件
- C# 数据类型与PostgreSQL 数据类型映射
- 在Windows下利用MinGW编译FFmpeg
- tinyxml2简单使用
- Glide 加载图片背景变绿
- 微信平台BAE
- 解决ping不通win7主机
- 使用spring框架,用xml方式进行bean装配出现“The fully qualified name of the bean&#39;s class, except if it serves...”
- 25 Zabbix系统数据表结构介绍
- Android MVP 架构一 View与Presenter
- 解决React Native使用Fetch API请求网络报Network request failed
- SUPERSOCKET 客户端
- Delphi实现图像文本旋转特效完整代码
- 《精通Python设计模式》学习之工厂方法
- fileupload 上传execl文件的一些操作
- 如鹏网学习笔记(六)ADO.Net基础
- luogu 1066 引水入城(bfs+贪心)
- highcharts配置的效果如下