UVA10529 Dumb Bones

题意:

给出放一个多米诺骨牌,向左向右倒的概率,求要放好n个骨牌,需要放置的骨牌的期望次数。

Sample Input

10 0.25 0.25
10 0.1 0.4
10 0.0 0.5
0

Sample Output

46.25
37.28
20.00

 

概率dp+区间dp

可以f[i]表示放了i块最少期望的次数

则对于位置j左边一个  有 f[i]=min(  f[j]+f[i-j-1]+(1+pl*f[j]+pr*f[i-j-1])/(1-pl-pr))

O(n^2)枚举中间点即可

然后某毒瘤一本通上说,这个东西是凹的

所以可以记录每次决策的j得到O(n)的算法

 


1
说点什么

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
maoxiangui Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
maoxiangui
游客
maoxiangui

QAQ怎么还不更新博客