POJ 3156 Interconnect

MayFlyyh | Hash, 期望 | 2018-08-11
> 现在有n个点,给你m条边,每次随机选2个点连边(可能选已经连过的)并且花费1个代价,求使n点联通的期望最小代价。 --- 本题关心每个联通块的规模,但不关心每个联通块具体的点。 然后根据规模记忆化搜索,因为规模无法正常表示成值,所以每次hash一下当前dp的状态,然后记忆化搜索看是否已经算过并返回答案。 对于每个联通块,有两种情况,... [阅读全文]

BZOJ1426 收集邮票

MayFlyyh | DP, 期望 | 2018-07-12
> 1426: 收集邮票 > Time Limit: 1 Sec Memory Limit: 162 MB > Description > 有n种不同的邮票,皮皮想收集所有种类的邮票。唯一的收集方法是到同学凡凡那里购买,每次只能买一张,并且 买到的邮票究竟是n种邮票中的哪一种是等概率的,概率均为1/n。但是由于凡凡也很喜欢邮票,所以皮皮购买第k 张邮票需要支付k元钱。现在皮皮手中没有邮票... [阅读全文]

BZOJ1076 [SCOI2008]奖励关

MayFlyyh | DP, 期望 | 2018-07-12
> BZOJ 1076: [SCOI2008]奖励关 > Time Limit: 10 Sec Memory Limit: 128 MB > Description   你正在玩你最喜欢的电子游戏,并且刚刚进入一个奖励关。在这个奖励关里,系统将依次随机抛出k次宝物, 每次你都可以选择吃或者不吃(必须在抛出下一个宝物之前做出选择,且现在决定不吃的宝物以后也不能再吃)。 宝物一共有n种,系统每次抛出这... [阅读全文]

BZOJ1415 [Noi2005]聪聪和可可

MayFlyyh | DP, 期望 | 2018-07-12
### BZOJ1415 [Noi2005]聪聪和可可 ![BZOJ1415 [Noi2005]聪聪和可可](https://www.lydsy.com/JudgeOnline/images/1415_1.jpg) 首先要预处理处当前聪聪在i点,可可在j点的时候聪聪下一步要走到哪里(这我都没想出来。。。 然后就比较简单了,根据套路,这个聪聪在x节点的期望应该是可可在j节点走到各种地方后,聪聪跟上的期望,当然也要算出可... [阅读全文]
Ɣ回顶部