前言
传送门 :
思路
题目描述显然使用状态压缩表示每条鱼是否被吃,然后再使用概率 d p dp dp计算即可
状态表示 :
d
p
[
s
t
a
t
e
]
dp[state]
dp[state] 表示当前
s
t
a
t
e
state
state的存活概率
状态转移 :
d
p
[
i
]
=
d
p
[
i
∣
(
1
<
<
j
−
1
)
]
∗
p
[
k
]
[
j
]
/
(
1.0
∗
(
c
n
t
+
1
)
∗
c
n
t
/
2.0
)
dp[i] = dp[i|(1
