【BZOJ4008】[HNOI2015]亚瑟王
2024-09-05 08:05:52
【BZOJ4008】[HNOI2015]亚瑟王
题面
题解
由期望的线性性
可以知道,把所有牌打出的概率乘上它的伤害加起来就是答案
记第$i$张牌打出的概率为$fp[i]$
则
$$ ans=\sum_{i=0}^{n-1}d[i]*fp[i] $$
题目转化为求所有的$fp[i]$
如何求呢?
可以容易地知道
$$ fp[0]=1-(1-p[i])^r $$
这就是所有轮都打不出的概率
那么后面的$fp$怎么办?
发现因为有“打完牌结束该轮”的条件
不好直接算出后面的概率
这时候我们把$dp$拿出来。
设$f[i][j]$表示前$r$轮中,前$i$张卡一共出了$j$张的概率
那么假设我们知道了所有$f[i][j]$如何求$fp$?
和$fp[0]$类似,我们有
$$ fp[i]=\sum_{j=0}^{r}f[i - 1][j]×(1-(1-p[i])^{r-j}) $$
那么怎么求出$f$呢
我们由第$i$张牌最终选没选讨论一下
有
$$ 1.f[i][j]+=f[i-1][j]*(1-p[i])^{r-j}(i>0)\\ 2.f[i][j]+=f[i-1][j-1]*(1-(1-p[i])^{r-j+1})(i>0,j>0) $$
这题就差不多解决了
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAX_N = 250;
const int MAX_R = 140;
int N, R;
double p[MAX_N], d[MAX_N], pw[MAX_N][MAX_R];
double f[MAX_N][MAX_R], fp[MAX_N];
void Prepare() {
for (int i = 0; i < N; i++) {
pw[i][0] = 1.0;
for (int j = 1; j <= R; j++) pw[i][j] = (1.0 - p[i]) * pw[i][j - 1];
}
}
void solve() {
memset(f, 0, sizeof(f));
memset(fp, 0, sizeof(fp));
f[0][0] = pw[0][R];
f[0][1] = fp[0] = 1 - f[0][0];
for (int i = 1; i < N; i++) {
for (int j = 0; j <= R; j++) {
f[i][j] += f[i - 1][j] * pw[i][R - j];
if (j > 0) f[i][j] += f[i - 1][j - 1] * (1.0 - pw[i][R - j + 1]);
}
}
for (int i = 1; i < N; i++)
for (int j = 0; j <= R; j++) fp[i] += f[i - 1][j] * (1.0 - pw[i][R - j]);
}
int main () {
int T; scanf("%d", &T);
while (T--) {
scanf("%d%d", &N, &R);
for (int i = 0; i < N; i++) scanf("%lf%lf", &p[i], &d[i]);
Prepare();
solve();
double ans = 0;
for (int i = 0; i < N; i++) ans += d[i] * fp[i];
printf("%0.10lf\n", ans);
}
return 0;
}
最新文章
- 二.持续集成之--WEB后台
- div内填内容
- linux 系统负载高 如何检查
- linux RPM、YUM
- Asp.Net正在中止线程引发的问题
- android通话时第二通电话呼叫等待提示音音量大小
- 使用Memory Analyzer tool(MAT)分析内存泄漏(一)
- WebOb的简单介绍
- VS2012无法创建项目:未找到与约束……匹配的导出
- 【MongoDB】The Access control of mongodb
- 【HDOJ】2268 How To Use The Car
- pat 1022 digital library
- sql 选取分组中的第一条,显示聚合以外的列,having字句的使用
- python学习笔记第一节
- DirectX11 With Windows SDK--02 顶点/像素着色器的创建、顶点缓冲区
- spark submit参数及调优
- TCP和UDP的区别和优缺点
- Android -------- MVC,MVP 和 MVVM 架构设计模式
- 编程输出杨辉三角的前10行---多维数组的应用---java实现
- 最新的裸机联想笔记本装win7系统/SSD(固态硬盘)上安装win7系统/联想K4450A i7装win7系统