【算法】期望DP+状压DP

【题解】f[i][j]表示第i轮，状态为j的期望得分。

期望DP一般倒着做，因为正着做的话会可能从很多状态都可以满足当前选择，需要双重枚举。

而如果倒着做的话，是已知当前状态枚举后面的选择，只需单重枚举。

倒着枚举，则f[i][j]表示当前第i轮状态为j，枚举第i+1轮的宝物得到状态j‘。

题目中出现了最优决策难以和期望DP结合，那么使用状压就可以避开决策问题。

得分的来源是枚举的宝物，所以正枚和倒枚没有本质区别，这也是套路。

【BZOJ】1076 [SCOI2008]奖励关