首页 > 代码库 > bzoj4008 亚瑟王 概率dp
bzoj4008 亚瑟王 概率dp
链接：http://www.lydsy.com/JudgeOnline/problem.php?id=4008
重述题意：卡牌有发动概率和伤害，每张卡牌只发动一次，按顺序遍历，给出轮数，求伤害期望。
神思路啊……我的脑子基本想不出来……
如果说正面刚，刚一天也刚不掉，我们换个思路，用f[i][j]表示第i张卡被遍历j次的概率。
这个概率可以分为两部分：
1、第i-1张卡被遍历j次且一直没发动。这一段公式为f[i-1][j]*(1-p[i-1])j。其中，p[i]表示第i张卡发动的概率。
2、第i-1张卡被遍历j+1次但已发动。这一段公式为f[i-1][j+1]*(1-(1-p[i-1])j)（至少发动一次的概率）。
那么，f[i][j]就是这两部分的和。
问题来了，一直在求概率，要求的期望呢？其实f[i][j]对期望的贡献，是遍历j次且发动了的概率与伤害的乘积，也就是f[i][j]*(1-(1-p[i])j)*d[i]，其中d[i]为第i张卡的伤害。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 typedef long double LLF; 8 const int maxn=225,maxr=135; 9 LLF f[maxn][maxr],ans; 10 double p[maxn]; 11 int n,r,d[maxn]; 12 int haha() 13 { 14 //freopen("arthur.in","r",stdin); 15 //freopen("arthur.out","w",stdout); 16 int t;scanf("%d",&t); 17 while(t--) 18 { 19 memset(f,0,sizeof(f)); 20 scanf("%d%d",&n,&r); 21 for(int i=1;i<=n;i++)scanf("%lf%d",&p[i],&d[i]); 22 f[0][r]=1; 23 for(int i=1;i<=n;i++) 24 for(int j=1;j<=r;j++) 25 { 26 f[i][j]=f[i-1][j]*pow(1-p[i-1],j)+f[i-1][j+1]*(1-pow(1-p[i-1],j+1)); 27 ans+=f[i][j]*d[i]*(1-pow(1-p[i],j)); 28 } 29 printf("%0.10lf\n",(double) ans); 30 ans=0; 31 } 32 } 33 int sb=haha(); 34 int main(){;}
bzoj4008 亚瑟王 概率dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。