RainAir
My OI Blog
RainAir
「NOIP2017」宝藏

题目链接

Luogu P3959

这一题有两种做法:状压dp和模拟退火

解题思路

看到这一道题目的时候,我的第一反应就是:裸的Prim啊!

但仔细思考了一下,发现事情没有那么简单:

长度和层数都对后面的结果有影响,所以不能贪心的求Prim,贪心会导致局部最优解,最终分数会很低。

然后看到了N很小,所以就用了一种伪·模拟退火来做这一道题。

思想就是我们选取一个随机数,给定被淘汰的状态一个“复活”的机会,来借此逃避局部最优解。

也就是伪·模拟退火。

代码

状压做法

看到 $n$ 这么小我们当然要考虑状压dp了。
设计状态 $f_{i,S}$ 表示当前宝藏屋打通状态为 $S$,已经打到了第 $i$ 层的最小代价。
显然转移枚举这一次打通哪一个并且和新打通的在同一层都有多少个就可以了。

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/125
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「NOIP2017」宝藏
题目链接 Luogu P3959 这一题有两种做法:状压dp和模拟退火 解题思路 看到这一道题目的时候,我的第一反应就是:裸的Prim啊! 但仔细思考了一下,发现事情没有那么简单: …
扫描二维码继续阅读
2018-11-08
标签
近期评论