BZOJ 4008 【HNOI2015】 亚瑟王

时间:2023-07-18 18:09:38

题目链接:亚瑟王

  这道题好神啊TAT……果然我的dp还是太弱了……

  一开始想了半天的直接dp求期望,结果最后WA的不知所云……

  最后去翻了题解,然后发现先算概率,再求期望……新姿势\(get\)。

  我们不妨把\(r\)轮看做\(r\)次出牌机会,然后令\(f_{i,j}\)表示考虑完前\(i\)张牌,还剩\(j\)次机会的概率。

  然后我们从前往后一张张牌考虑过去。对第$i$张牌,枚举还剩$j$次机会,单独考虑一下:

  若这张牌没有发动,那么概率为$(1-p_i)^jf_{i-1,j}$

  若这张牌发动了,那么就是在还剩\(j+1\)次机会的时候打出这张牌。由于每张牌最多发动一次,那么概率为$(1-(1-p_i)^j)f_{i-1,j+1}$

  于是我们得到了转移方程:$$f_{i,j}=(1-p_i)^jf_{i-1,j}+(1-(1-p_i)^j)f_{i-1,j+1}$$

  然后预处理出$(1-p_i)^j$,一路推过去即可。

  最后再枚举第$i$张牌在还剩$j$次机会时打出,用概率来算一下期望。当然这一步也可以在$dp$的时候就顺便解决。

  下面贴代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define N 230 using namespace std;
typedef double llg; int T,n,r,a[N];
llg p[N],f[N][N],mi[N][N],ans; int main(){
File("a");
scanf("%d",&T);
for(int i=0;i<N;i++) mi[0][i]=mi[i][0]=1;
while(T--){
scanf("%d %d",&n,&r); ans=0;
for(int i=1;i<=n;i++){
scanf("%lf %d",&p[i],&a[i]);
mi[i][1]=1-p[i];
for(int j=2;j<=r+1;j++) mi[i][j]=mi[i][j-1]*(1-p[i]);
}
for(int i=0;i<=r;i++) f[0][i]=0;
for(int i=0;i<=n;i++) f[i][r+1]=0;
f[0][r]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<=r;j++){
f[i][j]=f[i-1][j]*mi[i][j];
f[i][j]+=f[i-1][j+1]*(1-mi[i][j+1]);
ans+=f[i-1][j+1]*(1-mi[i][j+1])*a[i];
}
printf("%.10lf\n",ans);
}
return 0;
}