收集卡牌
原先我的思路是爆搜,可以拿到10分…
1 |
|
但是这样会有非常多冗余的搜索…同时,我们想到当dfs超时时一般会使用dp算法进行优化。同时,在题干中也提到了最多有16种卡牌,而$2^{16}$这个级别完全可以使用状压dp。
对于此类问题,我们可以先看一下绿豆蛙的归宿,作为解题的基本思路和基本模板来处理。虽然用的是dp,但我觉得更像是剪枝过后的搜索,代码如下:
1 |
|
上面使用的是一种倒推的思想,依照上面的求解方式,对于解决这类问题应该更加容易去理解。
对于有关期望问题的求解,一般都会使用这样的形式,首先将所有的状态置为nan(memset double),再递归进行求解。
下面给出dp算法的求解思路:
设二维数组f[i][j]
,一维表示16种卡牌的拥有情况,第二维表示硬币数,二维数组的值为期望值。当当前拥有的卡牌种类数达标,或者加上硬币的数量达标之后,就应该增加期望值。
1 |
|
对于f[i][j]
的定义应该进行进一步说明,它代表的是当前卡牌的拥有情况i以及硬币拥有情况数j情况下所有情况的期望抽取结果(假设当前的概率为1)。当已经有集齐所有卡牌时,显然其期望是从最初抽取卡牌的次数。如果还没能集齐所有卡牌,那么就需要思考每种卡牌抽取的概率,将所有子期望相加。该做法也是基于基础的期望表达式:
$$
E(X)=E(p_1X_1+p_2X_2+p_3X_3+…)=p_1E(X_1)+p_2E(X_2)+p_3E(X_3)
$$
初看的确有些难理解,希望能通过这题对期望的计算有更深刻的认识。