[HNOI2015]亚瑟王
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
-------------------------------------------------------------------
真是神题啊...
原题可以认为是有j个机会，从左往右扫，每个人有p[i]的几率得到这个机会(每个机会相当于一轮游戏)
设f[i][j]表示前i个人，还剩j个机会的概率（这神一般的状态设计）
考虑转移：
f[i][j] * ((1-p[i])^j) -> f[i+1][j] (第i+1个人一个机会都没得到)
f[i][j] * (1-((1-p[i])^j)) -> f[i+1][j] (第i+1个人至少得到了一个机会，但是每个人最多只能得到一个机会，所以就认为他只得到了一个机会，多得到的可以认为是这个机会作废了，也就是游戏一轮没有人被选中的情况)
最后的答案就是∑(i=1,j)d[i]*∑(j=0,r)f[i-1][j]*(1-((1-p[i])^j))表明i-1的时候有j个机会且i至少得到了一个
-------------------------------------------------------------------
评论 (0)
