[luogu] CF16E Fish 状态压缩+概率dp

前言

传送门 :

思路

题目描述显然使用状态压缩表示每条鱼是否被吃,然后再使用概率 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