[HNOI2015]亚瑟王

-------------------------------------------------------------------
BZOJ4008
真是神题啊...
 
原题可以认为是有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至少得到了一个
-------------------------------------------------------------------