BZOJ 4008: [HNOI2015]亚瑟王 [DP 概率 !!!]

传送门

题意:

$r$轮$n$张卡牌,每一轮依次考虑每张卡牌,$p_i$概率发动造成$d_i$伤害后结束本轮或者继续考虑下一张

每张卡牌发动过之后以后都会跳过

求$r$轮之后的期望伤害


看了一节课出题人的做法,并不知道该怎么写代码,感觉带着除法精度好玄学....

发现网上的题解都是另一种做法

$f[i][j]$表示第$i$张牌被考虑了$j$次的概率

有两个转移:

$1.\ $上一张牌考虑了$j$次都不发动

$2.\ $上一张牌考虑了$j+1$次,之前$k$次不发动,第$k$次发动了,$a*\sum\limits_{k=0}^{j}{(1-a)^k}$等比数列求和

$f[i][j]=f[i-1][j]*(1-p_{i-1})^j\ +\ f[i-1][j+1]*(1-(1-p_{i-1})^{j+1})$

我现在还不太明白两种做法有什么联系

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=;
typedef double ld;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,r,d[N];
double x;
ld p[N],f[N][N];
ld g[N][N];
int main(){
freopen("in","r",stdin);
int T=read();
while(T--){
//memset(f,0,sizeof(f));
n=read();r=read();
for(int i=;i<=n;i++)
scanf("%lf",&x),p[i]=x,d[i]=read();
memset(f[],,sizeof(f[]));
f[][r]=;
ld ans=;
for(int i=;i<=r;i++) g[][i]=;
for(int i=;i<=n;i++) g[i][]=;
for(int i=;i<=n;i++)
for(int j=;j<=r;j++){
f[i][j]=f[i-][j]*g[i-][j];
if(j+<=r) f[i][j]+=f[i-][j+]*( -g[i-][j+] );
g[i][j]=g[i][j-]*(-p[i]);
ans+=f[i][j]*( -g[i][j] )*d[i];
}
printf("%.10lf\n",(double)ans);
}
}
上一篇:MySQL索引


下一篇:python datetime模块简单记录