Java教程

洛谷P2395题解

本文主要是介绍洛谷P2395题解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题面

看到数据范围显然是个状压DP。
考虑记录两个数组， \(dis\) 和 \(f\) 。\(dis\) 数组表示当前状态走了多少路程， \(f\) 数组表示当前状态有多少种走法。
显然 \(dis\) 数组可以随便推，在当前状态中随便取一位 \(p\) ，然后计算 \(dis_s=dis_{s-p}+dis_p\) 即可。
但是 \(f\) 数组较为难推。首先， \(f\) 数组可以参照 \(dis\) 数组的推法，但是，我们这次要用全部合法的 \(p\) 来进行转移，但是如果暴力枚举每一位 \(p\) 是否合法会T，所以我们要用一个trick，就是在写树状数组时用的 \(\operatorname{lowbit}\) 。 $$f_s=f_s+f_t, t\in s$$

代码

注:本题非常卡时空，所以不能 #define int ll 否则MLE。

这篇关于洛谷P2395题解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航