洛谷P3239 [HNOI2015]亚瑟王(期望dp)
2024-08-30 18:33:07
期望的姿势不是很高……据大佬说期望有一个线性性质,也就是说可以把每一张牌的期望伤害算出来然后再加起来就是总的期望伤害
因为每一张牌只能用一次,我们设$dp[i]$表示第$i$张牌被使用的概率,$d[i]$表示这一张牌的伤害,那么总伤害就是$$\sum_{i=1}^n dp[i]*d[i]$$
首先,第一张牌的概率是很好计算的,也就是$dp[1]=1-(1-p[i])^r$,就是说这张牌一直憋着不出
然后考虑之后的牌的概率怎么计算。首先牌选的顺序对答案是没有影响的,所以我们设$f[i][j]$表示$r$轮里在前$i$张牌中选了$j$张的概率。如果前面的$i-1$张牌里选了$j$张,那么有$j$轮不会考虑到第$i$张牌,有$r-j$轮会考虑到。那么我们枚举$j$,于是$$dp[i]=\sum_{j=1}^r f[i-1][j]*(1-(1-p[i])^{r-j})$$
然后只要我们能把$f[i][j]$求出来就好了。考虑如何转移,有两种情况,一种是第$i$张牌最终没有被选,那么$f[i][j]$由$f[i-1][j]$转移而来,不选的概率是$(1-p[i])^{r-j}$,即$$f[i][j]+=f[i-1][j]*(1-p[i])^{r-j}$$
还有一种情况是第$i$张牌被选了,那么是由$f[i-1][j-1]$转移过来,这张牌被选的概率是$(1-(1-p[i])^{r-j+1})$,即$$f[i][j]+=f[i-1][j-1]*(1-(1-p[i])^{r-j+1})$$
然后只要转移就好了
然后代码里预处理了$1-p[i]$的幂
//minamoto
#include<bits/stdc++.h>
using namespace std;
const int N=;
int n,r,d[N];double p[N],dp[N],pow1p[N][N];
void init(){
for(int i=;i<=n;++i){
pow1p[i][]=;
for(int j=;j<=r;++j)
pow1p[i][j]=pow1p[i][j-]*(-p[i]);
}
}
double f[N][N];
void solve(){
memset(f,,sizeof(f)),memset(dp,,sizeof(dp));
f[][]=pow1p[][r],f[][]=dp[]=-f[][];
for(int i=;i<=n;++i)
for(int j=;j<=r;++j){
dp[i]+=f[i-][j]*(-pow1p[i][r-j]);
f[i][j]+=f[i-][j]*pow1p[i][r-j];
if(j) f[i][j]+=f[i-][j-]*(-pow1p[i][r-j+]);
}
double res=;
for(int i=;i<=n;++i) res+=dp[i]*d[i];
printf("%.10lf\n",res);
}
int main(){
// freopen("testdata.in","r",stdin);
int T;scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&r);
for(int i=;i<=n;++i) scanf("%lf%d",&p[i],&d[i]);
init(),solve();
}
return ;
}
最新文章
- Django入门1
- mysql exists 和 in的效率比较
- 2016百度之星-初赛(Astar Round2A)AII X
- java 堆栈 静态
- Android小项目之十二 设置中心的界面
- Apache与Tomcat整合
- C++函数中那些不可以被声明为虚函数的函数
- 深和学习导航CSS样式
- ios电话监听状态
- spring mvc 与 jasper Report集成
- React-Native 之 项目实战(四)
- 实战开发-》融云tp3.2.3
- linux下ftp命令的安装与使用
- L1正则化比L2正则化更易获得稀疏解的原因
- 【自动化测试&;爬虫系列】Selenium Webdriver
- Python基础【第二篇】
- C语言操作符
- Python基础(下)
- Django之MVC和MTV
- mybatis Mapper XML 映射文件