首页 > 代码库 > BZOJ 4008 【HNOI2015】 亚瑟王
BZOJ 4008 【HNOI2015】 亚瑟王
题目链接：亚瑟王
这道题好神啊TAT……果然我的dp还是太弱了……
一开始想了半天的直接dp求期望，结果最后WA的不知所云……
最后去翻了题解，然后发现先算概率，再求期望……新姿势\(get\)。
我们不妨把\(r\)轮看做\(r\)次出牌机会，然后令\(f_{i,j}\)表示考虑完前\(i\)张牌，还剩\(j\)次机会的概率。
然后我们对第$i$张牌，枚举还剩几次机会，单独考虑一下：
若这张牌没有发动，那么概率为$f_{i-1,j}*(1-p_i)^j$
若这张牌在剩下的$j$轮发动，由于每张牌最多发动一次，那么概率为$f_{i-1,j+1}*(1-(1-p_i)^j)$
并且第$i$张牌在还剩$j$次机会时发动的概率就是$f_{i-1,j+1}*(1-(1-p_i)^j)$
于是预处理出$(1-p_i)^j$，一路推过去即可。
下面贴代码：
#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;
}
BZOJ 4008 【HNOI2015】 亚瑟王
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。