题意:
小吃中有N种卡片,每种卡片 i 出现的概率为 pi ,一袋小吃有可能没有卡片,但最多有一张.问集齐所有卡片需要购买小吃的袋数期望.
思路:
1.用状压dp,dp[ s ]表示在s状态时,集齐所需要的袋数期望.
s = 11111表示N = 5时集齐的状态,此时dp[ s ] = 0;
注意求期望的题,对于dp的定义一般都是从终态转移到初态,也就是反着求.
因为"期望"是
确定事件的结果 * 该事件发生的概率 = 平均来看尝试一次可以得到的结果,即期望
若是在s1状态得到一张卡片转移到了s2,那么s2是一个确定的状态,而在s1时则有多种可能性.由此可以理解反着求的合理......
阅读全文